Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Mirka, Renee; Williamson, David P. https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-165533
URL:

;

An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut

pdf-format:


Abstract

We experimentally evaluate the performance of several Max Cut approximation algorithms. In particular, we compare the results of the Goemans and Williamson algorithm using semidefinite programming with Trevisan’s algorithm using spectral partitioning. The former algorithm has a known .878 approximation guarantee whereas the latter has a .614 approximation guarantee. We investigate whether this gap in approximation guarantees is evident in practice or whether the spectral algorithm performs as well as the SDP. We also compare the performances to the standard greedy Max Cut algorithm which has a .5 approximation guarantee and two additional spectral algorithms. The algorithms are tested on Erdős-Renyi random graphs, complete graphs from TSPLIB, and real-world graphs from the Network Repository. We find, unsurprisingly, that the spectral algorithms provide a significant speed advantage over the SDP. In our experiments, the spectral algorithms return cuts with values which are competitive with those of the SDP.

BibTeX - Entry

@InProceedings{mirka_et_al:LIPIcs.SEA.2022.19,
  author =	{Mirka, Renee and Williamson, David P.},
  title =	{{An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16553},
  URN =		{urn:nbn:de:0030-drops-165533},
  doi =		{10.4230/LIPIcs.SEA.2022.19},
  annote =	{Keywords: Max Cut, Approximation Algorithms}
}

Keywords: Max Cut, Approximation Algorithms
Seminar: 20th International Symposium on Experimental Algorithms (SEA 2022)
Issue date: 2022
Date of publication: 11.07.2022
Supplementary Material: Software (Source Code): https://github.com/rmirka/max-cut-experiments archived at: https://archive.softwareheritage.org/swh:1:dir:eb13652be65db33c0ea45e66314475a4327cae0d


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI