Preprint
Oct 2026
Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs
We give a polynomial-time algorithm that achieves an $\alpha_{GW} + \tilde{\Omega}(1/d)$-approximation for Max 2-LIN(2) in weighted instances where each vertex appears in at most $d$ constraints. This improves on the $\alpha_{GW}+\tilde{\Omega}(1/d^2)$-approximation guarantee of [Hsieh-Kothari, ICALP'23]. We also show...
Rares-Darius Buhai, Suprovat Ghoshal, Pravesh K. Kothari et al.
· 0 citations