Speaker
Jun-Ting Hsieh
Description
Jun-Ting Hsieh and Pravesh Kothari
Abstract: In this note, we describe a $\alpha_{GW} + \tilde{\Omega}(1/d^2)$-factor approximation algorithm for Max-Cut on weighted graphs of degree at most $d$. Here, $\alpha_{GW} \approx 0.878$ is the worst-case approximation ratio of the Goemans-Williamson rounding for Max-Cut. This improves on previous results for unweighted graphs by Feige, Karpinski, and Langberg and Floren. Our guarantee is obtained by a tighter analysis of the solution obtained by applying a natural local improvement procedure to the Goemans-Williamson rounding of the basic SDP strengthened with triangle inequalities.