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.