| 1. |
- Ambuehl, Christoph, et al.
(författare)
-
INAPPROXIMABILITY RESULTS FOR MAXIMUM EDGE BICLIQUE, MINIMUM LINEAR ARRANGEMENT, AND SPARSEST CUT
- 2011
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 40:2, s. 567-596
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approximation scheme, unless NP-complete problems can be solved in randomized subexponential time. Furthermore, we show that the same techniques can be used for the Maximum Edge Biclique problem, for which we obtain a hardness factor similar to previous results but under a more standard assumption.
|
|
| 2. |
- Andersson, Arne, et al.
(författare)
-
Tight bounds for searching a sorted array of strings
- 2000
-
Ingår i: SIAM journal on computing (Print). - 0097-5397 .- 1095-7111. ; 30:5, s. 1552-1578
-
Tidskriftsartikel (refereegranskat)abstract
- Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection [GRAPHICS] characters in the worst case.
|
|
| 3. |
- Austrin, Per, et al.
(författare)
-
(2 + ϵ)-SAT is NP-hard
- 2017
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial and Applied Mathematics Publications. - 0097-5397 .- 1095-7111. ; 46:5, s. 1554-1573
-
Tidskriftsartikel (refereegranskat)abstract
- We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width w and the guarantee that there exists an assignment satisfying at least g = [w/2]-1 literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-Sat. Viewing 2-Sat 2 P as tractability of Sat when 1 in 2 literals are true in every clause, and NP-hardness of 3-Sat as intractability of Sat when 1 in 3 literals are true, our result shows, for any fixed ϵ > 0, the difficulty of finding a satisfying assignment to instances of "(2 + ϵ)-Sat" where the density of satisfied literals in each clause is guaranteed to exceed 1/2+ϵ. We also strengthen the results to prove that, given a (2k +1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k +1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy. Finally, we prove a general result showing the intractability of promise constraint satisfaction problems based on the paucity of certain "weak polymorphisms." The core of the above hardness results is the claim that the only weak polymorphisms in these particular cases are juntas depending on few variables.
|
|
| 4. |
- Austrin, Per, et al.
(författare)
-
Randomly supported independence and resistance
- 2011
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 40:1, s. 1-27
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that for any positive integers q and k there is a constant c(q,k) such that a uniformly random set of c(q,k)n(k) log n vectors in [q](n) with high probability supports a balanced k-wise independent distribution. In the case of k <= 2 a more elaborate argument gives the stronger bound, c(q,k)n(k). Using a recent result by Austrin and Mossel, this shows that a predicate on t bits, chosen at random among predicates accepting c(q,2)t(2) input vectors, is, assuming the unique games conjecture, likely to be approximation resistant. These results are close to tight: we show that there are other constants, c'(q,k), such that a randomly selected set of cardinality c'(q,k)n(k) points is unlikely to support a balanced k-wise independent distribution and, for some c > 0, a random predicate accepting ct(2)/logt input vectors is nontrivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the unique games conjecture, any predicate on t Boolean inputs accepting at least (32/33).2(t) inputs is approximation resistant. The results extend from balanced distributions to arbitrary product distributions.
|
|
| 5. |
- Austrin, Per
(författare)
-
TOWARDS SHARP INAPPROXIMABILITY FOR ANY 2-CSP
- 2010
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 39:6, s. 2430-2463
-
Tidskriftsartikel (refereegranskat)abstract
- We continue the recent line of work on the connection between semidefinite programming (SDP)-based approximation algorithms and the unique games conjecture. Given any Boolean 2-CSP (or, more generally, any Boolean 2-CSP with real-valued "predicates"), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. Furthermore, we give an SDP-based approximation algorithm and show that the approximation ratio of this algorithm on a certain restricted type of instances is exactly the inapproximability ratio yielded by our hardness result. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that Max 2-AND is unique games-hard to approximate within 0.87435. This improves upon the best previous hardness of alpha(GW) + epsilon approximate to 0.87856 and comes very close to matching the approximation ratio of the best algorithm known, 0.87401. It also establishes that balanced instances of Max 2-AND, i.e., instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor aGW and that Max Cut is not the hardest 2-CSP.
|
|
| 6. |
- Barak, B., et al.
(författare)
-
Making the long code shorter
- 2015
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial and Applied Mathematics. - 0097-5397 .- 1095-7111. ; 44:5, s. 1287-1324
-
Tidskriftsartikel (refereegranskat)abstract
- The long code is a central tool in hardness of approximation especially in questions related to the Unique Games Conjecture. We construct a new code that is exponentially more efficient but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results including the following: (1) For any ε > 0, we show the existence of an n-vertex graph G where every set of o(n) vertices has expansion 1-ε but G's adjacency matrix has more than exp(logδ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak, and Steurer [Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 563-572] who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. (2) A gadget that reduces Unique Games instances with linear constraints modulo K into instances with alphabet k with a blowup of kpolylog(K) , improving over the previously known gadget with blowup of kω(K). (3) An n-variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the semidefinite programming version of the Sherali-Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and Small-Set Expansion in certain related Cayley graphs and use this connection to derandomize the noise graph on the Boolean hypercube.
|
|
| 7. |
- Berkholz, Christoph, et al.
(författare)
-
Supercritical space-width trade-offs for resolution
- 2020
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 49:1, s. 98-118
-
Tidskriftsartikel (refereegranskat)abstract
- We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [E. Ben-Sasson, SIAM J. Comput., 38 (2009), pp. 2511-2525], and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [A.A. Razborov, J. ACM, 63 (2016), 16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [E. Ben-Sasson and J. Nordström, Short proofs may be spacious: An optimal separation of space and length in resolution, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS '08), 2008, pp. 709-718].
|
|
| 8. |
- Bernstein, Aaron, et al.
(författare)
-
Distributed exact weighted all-pairs shortest paths in randomized near-linear time
- 2023
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 52:2, s. 112-127
-
Tidskriftsartikel (refereegranskat)abstract
- In the distributed all-pairs shortest paths problem, every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity). The problem admits a (1 + o(1))-approximation Θ(n)-time algorithm and a nearly tight Ω(n) lower bound [D. Nanongkai, STOC'14, ACM, New York, 2014, pp. 565-573; C. Lenzen and B. Patt-Shamir, PODC'15, ACM, New York, 2015, pp. 153-162]. (Θ, Oand Ωhide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios (C. Lenzen and D. Peleg, PODC, ACM, New York, 2013, pp. 375-382; S. Holzer and R. Wattenofer, PODC, ACM, New York, 2012, pp. 355-364; D. Peleg, L. Roditty, and E. Tal, ICALP, Springer, Berlin, 2012, pp. 660-672; D. Nanongkai, STOC, ACM, New York, 2014, pp. 565-573-672). For the exact case, Elkin [STOC'17, ACM, New York, 2017, pp. 757-790] presented an O(n5/3 log2/3 n) time bound, which was later improved to O(n5/4) [C.-C. Huang, D. Nanongkai, T. Saranurak, FOCS'17, IEEE Computer Society, Los Alamitos, CA, 2017, pp. 168-179]. It was shown that any superlinear lower bound (in n) requires a new technique [K. Censor-Hillel, S. Khoury, A. Paz, DISC'17, LIPIcs Leibniz Int. Proc. Inform., Vol. 91, Schloss-Dagstuhl, Wadern, Germany, 2017, 10], but otherwise it remained widely open whether there exists a O(n)-time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) O(n)-time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous O(n5/4) bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous O(n5/4) bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in {1, 2, . . ., poly(n)}). As far as we know, ours is the first o(n2) algorithm that only requires unidirectional communication. For arbitrary weights, the previous state-of-the-art required O(n4/3) time [U. Agarwal and V. Ramachandran, IPDPS 2019, IEEE Computer Society, Los Alamitos, CA, 2019, and SPAA 2020, ACM, New York, 2020, pp. 11-21]. Our algorithm is extremely simple and relies on a new technique called random filtered broadcast. Given any sets of nodes A, B ⊆ V and assuming that every b ∊ B knows all distances from nodes in A, and every node v ∊ V knows all distances from nodes in B, we want every v ∊ V to know DistThroughB(a, v) = minb∊B dist(a, b) + dist(b, v) for every a ∊ A. Previous works typically solve this problem by broadcasting all knowledge of every b ∊ B, causing superlinear edge congestion and time. We show a randomized algorithm that can reduce edge congestions and thus solve this problem in O(n) expected time.
|
|
| 9. |
- Bhattacharya, Sayan, et al.
(författare)
-
DETERMINISTIC NEAR-OPTIMAL APPROXIMATION ALGORITHMS FOR DYNAMIC SET COVER
- 2023
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 52:5, s. 1132-1192
-
Tidskriftsartikel (refereegranskat)abstract
- In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min\{O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = \Omega(log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537-550]. In this paper we consider the low-frequency range, when f = O(log n), and obtain deterministic algorithms with a (1 + \epsilon)f-approximation ratio and the following guarantees on the update time. (1) O ((f/\epsilon) \cdot log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206-218]. In contrast, the only result with O(f)-approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114-125], who designed a randomized (1 + \epsilon)f-approximation algorithm with O((f2 /\epsilon) \cdot log n) amortized update time. (2) O \bigl(f2 /\epsilon3 + (f/\epsilon2) \cdot log C\bigr) amortized update time: This result improves the above update time bound for most values of f in the low-frequency range, i.e., f = o(log n). It is also the first result that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + \epsilon)-approximate minimum vertex cover in O(1/\epsilon2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872-1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/\epsilon3) \cdot log2(Cn)) worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3 n/\sansp\sanso\sansl\sansy(\epsilon)) worst-case update time for the unweighted dynamic vertex cover problem (i.e., when f = 2 and C = 1) of Bhattacharya, Henzinger, and Nanongkai [Fully dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst case update time, in Proceedings SODA 2017, SIAM, pp. 470-489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema.
|
|
| 10. |
- Björklund, Andreas
(författare)
-
Determinant Sums for Undirected Hamiltonicity
- 2014
-
Ingår i: SIAM Journal on Computing. - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 43:1, s. 280-299
-
Tidskriftsartikel (refereegranskat)abstract
- We present a Monte Carlo algorithm for Hamiltonicity detection in an $n$-vertex undirected graph running in $O(1.657^{n})$ time. To the best of our knowledge, this is the first superpolynomial improvement on the worst case runtime for the problem since the $O^*(2^n)$ bound established for the traveling salesman problem (TSP) over 50 years ago [R. Bellman, J. Assoc. Comput. Mach., 9 (1962), pp. 61--63], [M. Held and R. M. Karp, J. Soc. Indust. Appl. Math., 10 (1962), pp. 196--210]. ($O^*(f(n))$ suppresses polylogarithmic functions in $f(n)$). It answers in part the first open problem in Woeginger's 2003 survey on exact algorithms for NP-hard problems. For bipartite graphs, we improve the bound to $O^*(\sqrt{2}^n)\subset O(1.415^{n})$ time. Both the bipartite and the general algorithm can be implemented to use space polynomial in $n$. We combine several recently resurrected ideas to get the results. Our main technical contribution is a new algebraic characterization of Hamiltonian graphs. We introduce an extension of Hamiltonicity called Labeled Hamiltonicity and relate it to a Labeled Cycle Cover Sum in which we are set to count weighted arc labeled cycle covers over a finite field of characteristic two. The Labeled Cycle Cover Sum can be evaluated efficiently via determinants.
|
|
