Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP

Abstract

We describe an $\tilde{\hat{I}}\text{c◯}(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 $({\hat{I}}_{\star }^2+\tilde{\hat{I}}\text{c◯}(1/d^2))$-factor approximation algorithm for bounded-degree MAX 2-SAT instances, where ${\hat{I}}_{\star }^2$ is the UGC-optimal approximation ratio for MAX 2-SAT achieved by the LLZ algorithm. Our result generalizes an $(\hat{I}{\pm }_{GW}+\tilde{\hat{I}}\text{c◯}(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

Topics & keywords