Advertisement
Published in:
2012 | OriginalPaper | Chapter
New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
Author : Alexander Golovnev
Published in: Parameterized and Exact Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
MAX-2-SAT and MAX-2-CSP are important NP-hard optimization problems generalizing many graph problems. Despite many efforts, the only known algorithm (due to Williams) solving them in less than 2
n
steps uses exponential space. Scott and Sorkin give an algorithm with
$2^{n(1-\frac{2}{d+1})}$
time and polynomial space for these problems, where
d
is the average variable degree. We improve this bound to
$O^*(2^{n(1-\frac{10/3}{d+1})})$
for MAX-2-SAT and
$O^*(2^{n(1-\frac{3}{d+1})})$
for MAX-2-CSP. We also prove stronger upper bounds for
d
bounded from below. E.g., for
d
≥ 10 the bounds improve to
$O^*(2^{n(1-\frac{3.469}{d+1})})$
and
$O^*(2^{n(1-\frac{3.221}{d+1})})$
, respectively. As a byproduct we get a simple proof of an
$O^*(2^\frac{m}{5.263})$
upper bound for MAX-2-CSP, where m is the number of constraints. This matches the best known upper bound w.r.t.
m
due to Gaspers and Sorkin.