Home

Семинар 30 апреля 2004 года

Пятница, 30 апреля, комната 106. Начало в 18:00.

Докладчик: С. Федин.

Тема: Алгоритм Р.Вильямса для MAX-CSP, MAX-2-SAT, MAX-CUT,.

Abstract

Доклад по статье: Ryan Williams, "A new algorithm for optimal constraint satisfaction and its implications"

We present a novel method for exactly solving (in fact, counting solution to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), wich gives the first exponential improvement over trivial algorithm; mor precisely, it is a constant factor improvement in the base of the runtime exponent. In the case where constraints have arbitary weights, there is $(1+ e)$-approximation with roughly the same runtime, modulo polynomial factors. Our algorithm may be used to count the number of optima MAX-2-SAT and MAX-CUT instances in $O(m^3*2^{wn/3})$ time, where $w < 2.376$ is the matrix product exponent over a ring. This is the first known algorithm solving MAX-2-SAT and MAX-CUT in probably less than c^n steps in the worst case, for some $c<2$; similar new results are obtained for related problems. Our main constraction 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 for solving 2-CSP optimization. As a collary, we prove that an $n^{o(k)}$-time k-clique algorithm impies $SNP subseteq DTIME[2^{o(n)}]$, for any $k(n) in o(sqrt(nover log n))$.

Futher extensions of our technique yield connections between the compexity of some (polynomial-time) high demensional geometry problems and that of some general NP-hard problems. For example, if there are sufficiently faster algorithms for computing the diameter n points in $l_1$, then there is $(2-epsilon)^n$ algorithm for MAX-LIN. Such a result may be construed as either lower bounds on these high-dimentional problems, or hope that better algorithms exist for more general NP-hard problems.