A string is called a square (resp. cube) if it is in the form of XX = X-2 (resp. XXX = X-3). Given a sequence S of length n, a fundamental problem studied in the literature is the problem of computing a longest subseq...
详细信息
ISBN:
(纸本)9783031439797;9783031439803
A string is called a square (resp. cube) if it is in the form of XX = X-2 (resp. XXX = X-3). Given a sequence S of length n, a fundamental problem studied in the literature is the problem of computing a longest subsequence of S which is a square or cube (i.e., the longest square/cubic subsequence problem). While the longest square subsequence (LSS) can be computed in O(n(2)) time, the longest cubic subsequence (LCubS) is only known to be solvable in O(n(5)) time, using the longest common subsequence of three strings (LCS-3) as a subroutine (which was much less studied compared with LCS for two strings, or LCS-2). To improve the running time for LCubS, we look at its complementary version and also investigate LCS-3 for three strings S-1, S-2, S-3, with input lengths m <= n(1) <= n(2) respectively. Firstly, we generalize an algorithm by Nakatsu et al. for LCS-2 to have an O(n(1)n(2)delta) algorithm for computing LCS-3, where delta is the minimum number of letters to be deleted in S-1 to have an LCS-3 solution for S-1, S-2 and S-3. This results in an O(k(3)n(2)) algorithm for LCubS, where k is the minimum number of letters deleted in S to have a feasible solution. Then, let R be the number of triples (i, j, k) that match in the input, i.e., S-1[i] = S-2[j] = S-3[k], we show that LCS-3 can be computed in O(n+ R log log n + R-2) time (n is the maximum length of the three input strings). Finally, we define the t-pseudo-subsequence of S under an integer parameter t, which is a string Z containing a subsequence S ' of S such that S ' can be obtained from Z by deleting at most t letters. Subsequently, we study the longest majority t-pseudo-subsequence (LMtPS) of S-i, i = 1..3, which is a t-pseudo-subsequence T = t(1)t(2) center dot center dot center dot t(K) of S-i, i = 1..3, with the maximum length K;moreover, when T is aligned with some subsequence S-i ''s of length K in S-i, i = 1..3, each t(j) matches at least two letters with S-i ', i = 1..3. We show that LMtPS of three
The goal of this thesis to contribute towards a computational complexity theory of statistical inference problems. In recent years, researchers have built evidence in favor of an emerging hypothesis that the class of ...
详细信息
The goal of this thesis to contribute towards a computational complexity theory of statistical inference problems. In recent years, researchers have built evidence in favor of an emerging hypothesis that the class of semi-definite programming (SDP) algorithms is optimal among for computationally efficient algorithms for a certain family of estimation problems. In this thesis, we present four main research efforts that refine this hypothesis and initiate preliminary efforts to go beyond it: • Optimal algorithms for private and robust estimation: We give the first polynomial-time algorithms for privately and robustly estimating a Gaussian distribution with optimal dependence on the dimension in the sample complexity. This adds the fundamental problem of private statistical estimation to a growing list of problems for which SDPs are optimal among polynomial-time algorithms. • Limitations of SDPs: Given independent standard Gaussian points in dimension d, for what values of (n, d) does there exist with high probability an origin-symmetric ellipsoid that simultaneously passes through all of the points? Based on strong numerical evidence, it was conjectured that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points n increases, with a sharp threshold at n ∼ d 2/4; we resolve this conjecture up to logarithmic factors. A corollary of this result is that a canonical SDP-based algorithm fails to successfully solve inference problems involving low-rank matrix decompositions, independent component analysis, and principal component analysis. • New algorithms for discrepancy certification: We initiate the study of the algorithmic problem of certifying lower bounds on the discrepancy of random matrices, which has connections to conjecturally-hard average-case problems such as negatively-spiked PCA, the number-balancing problem and refuting random constraint satisfaction problems. We give the first polynomial-time algorithms with non-trivial
We propose polynomial-time algorithms for finding nontrivial zeros of quadratic forms with four variables over rational function fields of characteristic 2. We apply these results to find prescribed quadratic subfield...
详细信息
ISBN:
(纸本)9781450386883
We propose polynomial-time algorithms for finding nontrivial zeros of quadratic forms with four variables over rational function fields of characteristic 2. We apply these results to find prescribed quadratic subfields of quaternion division algebras and zero divisors in M-2(D), the full matrix algebra over a division algebra, given by structure constants. We also provide an implementation of our results in MAGMA which shows that the algorithms are truly practical.
The separable convex resource allocation problem with nested bound constraints aims to allocate B units of resources to n activities to minimize a separable convex cost function, with lower and upper bounds on the tot...
详细信息
The separable convex resource allocation problem with nested bound constraints aims to allocate B units of resources to n activities to minimize a separable convex cost function, with lower and upper bounds on the total amount of resources that can be consumed by nested subsets of activities. We develop a new combinatorial algorithm to solve this model exactly. Our algorithm is capable of solving instances with millions of activities in several minutes. The running time of our algorithm is at most 73% of the running time of the current best algorithm for benchmark instances with three classes of convex objectives. The efficiency of our algorithm derives from a combination of constraint relaxation and divide and conquer based on infeasibility information. In particular, nested bound constraints are relaxed first;if the solution obtained violates some bound constraints, we show that the problem can be divided into two subproblems of the same structure and smaller sizes according to the bound constraint with the largest violation. Summary of Contribution. The resource allocation problem is a collection of optimization models with a wide range of applications in production planning, logistics, portfolio management, telecommunications, statistical surveys, and machine learning. This paper studies the resource allocation model with prescribed lower and upper bounds on the total amount of resources consumed by nested subsets of activities. These nested bound constraints are motivated by storage limits, time-window requirements, and budget constraints in various applications. The model also appears as a subproblem in models for green logistics and machine learning, and it has to be solved repeatedly. The model belongs to the class of computationally challenging convex mixed-integer nonlinear programs. We develop a combinatorial algorithm to solve this model exactly. Our algorithm is faster than the algorithm that currently has the best theoretical complexity in the literatu
The paper is concerned with the two-machine scheduling problem where each job is to be processed on the first-stage machine and after that on the second-stage machine. In order to be processed, each job requires stora...
详细信息
The paper is concerned with the two-machine scheduling problem where each job is to be processed on the first-stage machine and after that on the second-stage machine. In order to be processed, each job requires storage space that it seizes at the start of its processing on the first-stage machine and releases only at the completion of processing on the second-stage machine. The storage space is limited and its consumption varies from job to job. The goal is to minimise the time needed for the completion of all jobs. All instances of the considered scheduling problem are classified by means of five parameters. This leads to the sixty four families of instances. For each family, the paper establishes its computational complexity and, in the case of polynomial-time solvability, presents a polynomial-time algorithm, constructing an optimal schedule.
In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They de...
详细信息
In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They defined two stability notions, strongly stable noncrossing matching (SSNM) and weakly stable noncrossing matching (WSNM), depending on the strength of blocking pairs. They proved that a WSNM always exists and presented an O(n(2))-time algorithm to find one for an instance with n men and n women. They also posed open questions of the complexities of determining existence of an SSNM and finding a largest WSNM. In this paper, we show that both problems are solvable in polynomialtime. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete. This NP-completeness holds even if each person's preference list is of length at most two and ties appear in only men's preference lists. To complement this intractability, we show that the problem is solvable in polynomialtime if the length of preference lists of one side is bounded by one (but that of the other side is unbounded).
The complexity of graph isomorphism (GRAPHISO) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted ...
详细信息
The complexity of graph isomorphism (GRAPHISO) is a famous problem in computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (LISTISO) is NP-complete: for each u is an element of V(G), we are given a list L(u) subset of V(H) of possible images of u. After 35 years, we revive the study of this problem and consider which results for GraphIso can be modified to solve ListIso. We prove: 1) Under certain conditions, GI-completeness of a class of graphs implies NP-completeness of ListIso. 2) Several combinatorial algorithms for GraphIso can be modified to solve ListIso: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, and bounded treewidth graphs. 3) ListIso is NP-complete for cubic colored graphs with sizes of color classes bounded by 8 with all lists of size at most 3. (C) 2021 The Author(s). Published by Elsevier B.V.
This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, c...
详细信息
This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, community detection and hypothesis testing. For each problem, we review state-of-the-art results in the literature followed by general principles behind the optimal procedures that lead to minimax estimation and testing. This allows us to connect problems in network analysis to other statistical inference problems from a general perspective.
An s-club is a graph which has diameter at most s. Let G be a graph. A set of vertices D subset of V(G) is an s-club deleting (s-CD) set if each connected component of G - D is an s-club. In the s-CLUB CLUSTER VERTEX ...
详细信息
ISBN:
(纸本)9783030799878;9783030799861
An s-club is a graph which has diameter at most s. Let G be a graph. A set of vertices D subset of V(G) is an s-club deleting (s-CD) set if each connected component of G - D is an s-club. In the s-CLUB CLUSTER VERTEX DELETION (s-CVD) problem, the goal is to find an s-CD set with minimum cardinality. When s = 1, the s-CVD is equivalent to the well-studied CLUSTER VERTEX DELETION problem. On the negative side, we show that unless the Unique Games Conjecture is false, there is no (2 - epsilon)-algorithm for 2-CVD on split graphs, for any epsilon > 0. This contrast the polynomial-time solvability of CLUSTER VERTEX DELETION on split graphs. We show that for each s >= 2, s-CVD is NP-hard on bounded degree planar bipartite graphs and APX-hard on bounded degree bipartite graphs. On the positive side, we give a polynomial-time algorithm to solve s-CVD on trapezoid graphs, for each s >= 1.
We consider the two-sided stable matching setting in which there may be uncertainty about the agents' preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery m...
详细信息
We consider the two-sided stable matching setting in which there may be uncertainty about the agents' preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model-for each agent, there is a probability distribution over linear preferences, (2) compact indifference model-for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model-there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant.
暂无评论