LIPIcs.ICALP.2023.77.pdf
- Filesize: 0.6 MB
- 7 pages
In this note, we describe a α_GW + Ω̃(1/d²)-factor approximation algorithm for Max-Cut on weighted graphs of degree ⩽ d. Here, α_GW ≈ 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 [Feige et al., 2002] and Florén [Florén, 2016]. 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.
Feedback for Dagstuhl Publishing