zbMATH — the first resource for mathematics

A new algorithm for optimal 2-constraint satisfaction and its implications. (English) Zbl 1081.68095
Summary: We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm. More precisely, the runtime bound is a constant factor improvement in the base of the exponent: the algorithm can count the number of optima in MAX-2-SAT and MAX-CUT instances in $$O(m^{3}2^{\omega n/3})$$ time, where $$\omega < 2.376$$ is the matrix product exponent over a ring. When the constraints have arbitrary weights, there is a ($$1+\varepsilon$$)-approximation with roughly the same runtime, modulo polynomial factors. Our construction shows that improvement in the runtime exponent of either $$k$$-clique solution (even when $$k=3$$) or matrix multiplication over GF(2) would improve the runtime exponent for solving 2-CSP optimization.
Our approach also yields connections between the complexity of some (polynomial time) high-dimensional search problems and some NP-hard problems. For example, if there are sufficiently faster algorithms for computing the diameter of $$n$$ points in $$\ell _{1}$$, then there is an ($$2-\varepsilon)^{n}$$ algorithm for MAX-LIN. These results may be construed as either lower bounds on the high-dimensional problems, or hope that better algorithms exist for the corresponding hard problems.

MSC:
 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 68Q05 Models of computation (Turing machines, etc.) (MSC2010)
MAX-2-SAT
Full Text:
References:
 [1] Alber, J.; Gramm, J.; Niedermeier, R., Faster exact algorithms for hard problems: a parameterized point of view, Discrete math., 229, 3-27, (2001) · Zbl 0973.68256 [2] Alon, N.; Naor, M., Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Algorithmica, 16, 434-449, (1996) · Zbl 0857.68055 [3] Alon, N.; Yuster, R.; Zwick, U., Color-coding, Jacm, 42, 4, 844-856, (1995) · Zbl 0885.68116 [4] N. Bansal, V. Raman, Upper bounds for Max-Sat: further improved, in: Proc. ISAAC, Lecture Notes in Computer Science, Vol. 1741, Springer, Berlin, 1999, pp. 247-258. · Zbl 0971.68069 [5] M. Charikar, P. Indyk, R. Panigrahy, New algorithms for subset query, partial match, orthogonal range searching, and related problems, in: Proc. of ICALP, Lecture Notes in Computer Science, Vol. 2380, Springer, Berlin, 2002, pp. 451-462. · Zbl 1056.68512 [6] J. Chen, I. Kanj, Improved exact algorithms for MAX-SAT, in: Proc. of LATIN, Lecture Notes in Computer Science, Vol. 2286, Springer, Berlin, 2002, pp. 341-355. · Zbl 1059.68617 [7] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, Jsc, 9, 3, 251-280, (1990) · Zbl 0702.65046 [8] Dantsin, E.; Gavrilovich, M.; Hirsch, E.A.; Konev, B., MAX-SAT approximation beyond the limits of polynomial-time approximation, Ann. pure appl. logic, 113, 1-3, 81-94, (2001) · Zbl 0990.03006 [9] Gramm, J.; Hirsch, E.A.; Niedermeier, R.; Rossmanith, P., Worst-case upper bounds for MAX-2-SAT with application to MAX-CUT, Discrete appl. math., 130, 2, 139-155, (2003) · Zbl 1051.68078 [10] J. Gramm, R. Niedermeier, Faster exact solutions for Max2Sat, in: Proc. of CIAC, Lecture Notes in Computer Science, Vol. 1767, Springer, Berlin, 2000, pp. 174-186. · Zbl 0971.68598 [11] E.A. Hirsch. A $$2^{m / 4}$$-time algorithm for MAX-2-SAT: corrected version, Electronic Colloquium on Computational Complexity Report TR99-036, 2000. [12] Hirsch, E.A., Worst-case study of local search for MAX-k-SAT, Discrete appl. math., 130, 2, 173-184, (2003) · Zbl 1051.68079 [13] T. Hofmeister, U. Schöning, R. Schuler, O. Watanabe, A probabilistic 3-SAT algorithm further improved, in: Proc. of STACS, Lecture Notes in Computer Science, Vol. 2285, Springer, Berlin, 2002, pp. 192-202. · Zbl 1054.68138 [14] Horowitz, E.; Sahni, S., Computing partitions with applications to the knapsack problem, Jacm, 21, 277-292, (1974) · Zbl 0329.90046 [15] Itai, A.; Rodeh, M., Finding a minimum circuit in a graph, SIAM J. comput., 7, 4, 413-423, (1978) · Zbl 0386.68064 [16] Fedin, S.S.; Kulikov, A.S., A $$2^{| E | / 4}$$-time algorithm for MAX-CUT, J. math. sci., 126, 3, 1200-1204, (2005) · Zbl 1093.90070 [17] Mahajan, M.; Raman, V., Parameterizing above guaranteed values: MAXSAT and MAXCUT, J. algorithms, 31, 2, 335-354, (1999) · Zbl 0921.68052 [18] Nesetril, J.; Poljak, S., On the complexity of the subgraph problem, Comment. math. univ. carolin., 26, 2, 415-419, (1985) · Zbl 0571.05050 [19] Niedermeier, R.; Rossmanith, P., New upper bounds for maximum satisfiability, J. algorithms, 26, 63-88, (2000) · Zbl 0959.68049 [20] Paturi, R.; Pudlak, P.; Saks, M.E.; Zane, F., An improved exponential-time algorithm for k-SAT, Jacm, 52, 3, 337-364, (2005) · Zbl 1297.68217 [21] Raman, V.; Ravikumar, B.; Srinivasa Rao, S., A simplified NP-complete MAXSAT problem, Inform. process. lett., 65, 1-6, (1998) · Zbl 1339.68122 [22] Rivest, R., Partial match retrieval algorithms, SIAM J. comput., 5, 19-50, (1976) · Zbl 0331.68064 [23] Robson, M., Algorithms for maximum independent sets, J. algorithms, 7, 3, 425-440, (1986) · Zbl 0637.68080 [24] F. Ruskey. Simple combinatorial Gray codes constructed by reversing sublists, in: Proc. of Interat. Symp. on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 762, Springer, Berlin, 1993, pp. 201-208. · Zbl 0925.94101 [25] Schöning, U., A probabilistic algorithm for $$k$$-SAT and constraint satisfaction problems, (), 410-414 [26] Schroeppel, R.; Shamir, A., A $$T = O(2^{n / 2})$$, $$S$$=$$O(2^{n / 4})$$ algorithm for certain NP-complete problems, SIAM J. comput., 10, 3, 456-464, (1981) · Zbl 0462.68015 [27] Schuler, R., An algorithm for the satisfiability problem of formulas in conjunctive normal form, J. algorithms, 54, 1, 40-44, (2005) · Zbl 1090.68052 [28] A. Scott, G. Sorkin, Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances, in: Proc. of RANDOM-APPROX 2003, Lecture Notes in Computer Science, Vol. 2764, Springer, Berlin, 2003, pp. 382-395. · Zbl 1279.68108 [29] G.J. Woeginger, Exact algorithms for NP-hard problems: a survey, in: Combinatorial Optimization—Eureka! You shrink!, Lecture Notes in Computer Science, Vol. 2570, Springer, Berlin, 2003, pp. 185-207. · Zbl 1024.68529 [30] Zwick, U., All pairs shortest paths using bridging sets and rectangular matrix multiplication, Jacm, 49, 3, 289-317, (2002) · Zbl 1326.05157
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.