ECCC-Report TR04-032https://eccc.weizmann.ac.il/report/2004/032Comments and Revisions published for TR04-032en-usFri, 09 Apr 2004 21:33:31 +0300
Paper TR04-032
| A new algorithm for optimal constraint satisfaction and its implications |
Ryan Williams
https://eccc.weizmann.ac.il/report/2004/032We 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, it is a constant factor improvement in the base of the runtime exponent. In the case where constraints have arbitrary weights, there is a (1+\epsilon)-approximation with roughly the same runtime, modulo polynomial factors. Our algorithm may be used to 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. This is the first known algorithm solving MAX-2-SAT and MAX-CUT in provably less than c^n steps in the worst case, for some c < 2; similar new results are obtained for related problems. Our main construction may also be used to show that any 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. As a corollary, we prove that an n^{o(k)}-time k-clique algorithm implies SNP \subseteq DTIME[2^{o(n)}], for any k(n) \in o(\sqrt{n/\log n}).
Fri, 09 Apr 2004 21:33:31 +0300https://eccc.weizmann.ac.il/report/2004/032