\input zb-basic
\input zb-ioport
\iteman{io-port 06046500}
\itemau{Golovnev, Alexander}
\itemti{New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree.}
\itemso{Marx, D\'aniel (ed.) et al., Parameterized and exact computation. 6th international symposium, IPEC 2011, Saarbr\"ucken, Germany, September 6--8, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28049-8/pbk). Lecture Notes in Computer Science 7112, 106-117 (2012).}
\itemab
Summary: 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 \geq 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.
\itemrv{~}
\itemcc{}
\itemut{algorithm; satisfiability; maximum satisfiability; constraint satisfaction; maximum constraint satisfaction}
\itemli{doi:10.1007/978-3-642-28050-4\_9}
\end