{"ID":6537651,"CreatedAt":"2026-07-14T02:54:43.516908796Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.11050","arxiv_id":"2607.11050","title":"Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP","abstract":"We describe an $\\widetildeΩ(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 $(β_\\star + \\widetildeΩ(1/d^2))$-factor approximation algorithm for bounded-degree MAX 2-SAT instances, where $β_\\star$ is the UGC-optimal approximation ratio for MAX 2-SAT achieved by the LLZ algorithm. Our result generalizes an $(α_{GW} + \\widetildeΩ(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.","short_abstract":"We describe an $\\widetildeΩ(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 $(β_\\star + \\widetildeΩ(1/d^2))$-factor approximation algorith...","url_abs":"https://arxiv.org/abs/2607.11050","url_pdf":"https://arxiv.org/pdf/2607.11050v1","authors":"[\"Suprovat Ghoshal\",\"Neng Huang\",\"Euiwoong Lee\",\"Konstantin Makarychev\",\"Yury Makarychev\"]","published":"2026-07-13T03:25:22Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}