2026-09-10T09:44:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27745 2026-09-09T12:19:36Z ddc:004 open_access

Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP Ghoshal, Suprovat Huang, Neng Lee, Euiwoong Makarychev, Konstantin Makarychev, Yury MAX 2-SAT Approximation Algorithms Constraint Satisfaction Problems We describe an Ω̃(1/d⁴)-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 (β_⋆ + Ω̃(1/d²))-factor approximation algorithm for bounded-degree MAX 2-SAT instances, where β_⋆ is the UGC-optimal approximation ratio for MAX 2-SAT achieved by the LLZ algorithm [Lewin et al., 2002]. Our result generalizes an (α_GW + Ω̃(1/d²))-factor approximation algorithm for MAX CUT on graphs with degrees bounded by d, due to Hsieh and Kothari [Hsieh and Kothari, 2023]. Together with the state-of-the-art approximability results for MAX DI-CUT and MAX 2-AND [Brakensiek et al., 2023], our result suggests that similar improvements exist for bounded-degree instances of these problems as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Suprovat Ghoshal and Neng Huang and Euiwoong Lee and Konstantin Makarychev and Yury Makarychev 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.28 urn:nbn:de:0030-drops-277451 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.28 eng https://creativecommons.org/licenses/by/4.0/legalcode