License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.19
URN: urn:nbn:de:0030-drops-165533
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16553/
Mirka, Renee ;
Williamson, David P.
An Experimental Evaluation of Semidefinite Programming and Spectral Algorithms for Max Cut
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}
}
