A new algorithm for optimal 2-constraint satisfaction and its implications

Alber, 2001, Faster exact algorithms for hard problems: a parameterized point of view, Discrete Math., 229, 3, 10.1016/S0012-365X(00)00199-0 Alon, 1996, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, Algorithmica, 16, 434, 10.1007/BF01940874 Alon, 1995, Color-coding, JACM, 42, 844, 10.1145/210332.210337 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. 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. 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. Coppersmith, 1990, Matrix multiplication via arithmetic progressions, JSC, 9, 251 Dantsin, 2001, MAX-SAT approximation beyond the limits of polynomial-time approximation, Ann. Pure Appl. Logic, 113, 81, 10.1016/S0168-0072(01)00052-5 Gramm, 2003, Worst-case upper bounds for MAX-2-SAT with application to MAX-CUT, Discrete Appl. Math., 130, 139, 10.1016/S0166-218X(02)00402-X 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. E.A. Hirsch. A 2m/4-time algorithm for MAX-2-SAT: corrected version, Electronic Colloquium on Computational Complexity Report TR99-036, 2000. Hirsch, 2003, Worst-case study of local search for MAX-k-SAT, Discrete Appl. Math., 130, 173, 10.1016/S0166-218X(02)00404-3 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. Horowitz, 1974, Computing partitions with applications to the knapsack problem, JACM, 21, 277, 10.1145/321812.321823 Itai, 1978, Finding a minimum circuit in a graph, SIAM J. Comput., 7, 413, 10.1137/0207033 Fedin, 2005, A 2|E|/4-time algorithm for MAX-CUT, J. Math. Sci., 126, 1200, 10.1007/s10958-005-0101-7 Mahajan, 1999, Parameterizing above guaranteed values: MAXSAT and MAXCUT, J. Algorithms, 31, 335, 10.1006/jagm.1998.0996 Nesetril, 1985, On the complexity of the subgraph problem, Comment. Math. Univ. Carolin., 26, 415 Niedermeier, 2000, New upper bounds for maximum satisfiability, J. Algorithms, 26, 63, 10.1006/jagm.2000.1075 Paturi, 2005, An improved exponential-time algorithm for k-SAT, JACM, 52, 337, 10.1145/1066100.1066101 Raman, 1998, A simplified NP-complete MAXSAT problem, Inform. Process. Lett., 65, 1, 10.1016/S0020-0190(97)00223-8 Rivest, 1976, Partial match retrieval algorithms, SIAM J. Comput., 5, 19, 10.1137/0205003 Robson, 1986, Algorithms for maximum independent sets, J. Algorithms, 7, 425, 10.1016/0196-6774(86)90032-5 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. Schöning, 1999, A probabilistic algorithm for k-SAT and constraint satisfaction problems, 410 Schroeppel, 1981, A T=O(2n/2), S=O(2n/4) algorithm for certain NP-complete problems, SIAM J. Comput., 10, 456, 10.1137/0210033 Schuler, 2005, An algorithm for the satisfiability problem of formulas in conjunctive normal form, J. Algorithms, 54, 40, 10.1016/j.jalgor.2004.04.012 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. 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. Zwick, 2002, All pairs shortest paths using bridging sets and rectangular matrix multiplication, JACM, 49, 289, 10.1145/567112.567114