Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm

Jun Ting Hsieh, Pravesh K. Kothari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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é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.

Original languageEnglish (US)
Title of host publication50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
EditorsKousha Etessami, Uriel Feige, Gabriele Puppis
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772785
DOIs
StatePublished - Jul 2023
Externally publishedYes
Event50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Germany
Duration: Jul 10 2023Jul 14 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume261
ISSN (Print)1868-8969

Conference

Conference50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
Country/TerritoryGermany
CityPaderborn
Period7/10/237/14/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • approximation algorithm
  • Max-Cut
  • semidefinite programming

Fingerprint

Dive into the research topics of 'Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm'. Together they form a unique fingerprint.

Cite this