Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP

Abstract

We describe an $\tilde{\Omega }(1/d^4)$-improvement over threshold rounding schemes for a broad class of Boolean MAX 2-CSP instances in which every variable appears in at most $d$ constraints. In the case of MAX 2-SAT, we improve the ratio further and obtain an $({\beta }_{\star }+\tilde{\Omega }(1/d^2))$-factor approximation algorithm for bounded-degree MAX 2-SAT instances, where ${\beta }_{\star }$ is the UGC-optimal approximation ratio for MAX 2-SAT achieved by the LLZ algorithm. Our result generalizes an $({\alpha }_{GW}+\tilde{\Omega }(1/d^2))$-factor approximation algorithm for MAX CUT on graphs with degrees bounded by $d$, due to Hsieh and Kothari. Together with the state-of-the-art approximability results for MAX DI-CUT and MAX 2-AND, our result suggests that similar improvements exist for bounded-degree instances of these problems as well.

To appear in APPROX 26