Optimal Algorithms and Hardness for Max-Cut in Bounded Degree Graphs

Rares-Darius Buhai, Suprovat Ghoshal, Pravesh Kothari +4

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$ constrain…