@inproceedings{8fb8a18bb9e142e4b42d7a519422b346,
title = "Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm",
abstract = "In this note, we describe a αGW + Ω(1e /d2)-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 [1] and Flor{\'e}n [3]. 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.",
keywords = "approximation algorithm, Max-Cut, semidefinite programming",
author = "Hsieh, {Jun Ting} and Kothari, {Pravesh K.}",
note = "Publisher Copyright: {\textcopyright} Jun-Ting Hsieh and Pravesh K. Kothari.; 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 ; Conference date: 10-07-2023 Through 14-07-2023",
year = "2023",
month = jul,
doi = "10.4230/LIPIcs.ICALP.2023.77",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Kousha Etessami and Uriel Feige and Gabriele Puppis",
booktitle = "50th International Colloquium on Automata, Languages, and Programming, ICALP 2023",
address = "Germany",
}