License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2018.13
URN: urn:nbn:de:0030-drops-83098
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8309/
Go to the corresponding OASIcs Volume Portal

Newman, Alantha

Complex Semidefinite Programming and Max-k-Cut

pdf-format:
OASIcs-SOSA-2018-13.pdf (0.5 MB)

Abstract

In a second seminal paper on the application of semidefinite
programming to graph partitioning problems, Goemans and Williamson
showed in 2004 how to formulate and round a complex semidefinite program to give what is to date still the best-known approximation guarantee of .836008 for Max-3-Cut. (This approximation ratio was also achieved independently around the same time by De Klerk et
al..) Goemans and Williamson left open the problem of how to apply their techniques to Max-k-Cut for general k. They point out that it does not seem straightforward or even possible to formulate a good quality complex semidefinite program for the general Max-k-Cut problem, which presents a barrier for the further application of their techniques.

We present a simple rounding algorithm for the standard semidefinite
programmming relaxation of Max-k-Cut and show that it is equivalent to the rounding of Goemans and Williamson in the case of Max-3-Cut. This allows us to transfer the elegant analysis of Goemans and Williamson for Max-3-Cut to Max-k-Cut. For k > 3, the resulting approximation ratios are about .01 worse than the best known guarantees. Finally, we present a generalization of our rounding algorithm and conjecture (based on computational observations) that it matches the best-known guarantees of De Klerk et al.

BibTeX - Entry

@InProceedings{newman:OASIcs:2018:8309,
  author =	{Alantha Newman},
  title =	{{Complex Semidefinite Programming and Max-k-Cut}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{13:1--13:11},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Raimund Seidel},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8309},
  URN =		{urn:nbn:de:0030-drops-83098},
  doi =		{10.4230/OASIcs.SOSA.2018.13},
  annote =	{Keywords: Graph Partitioning, Max-k-Cut, Semidefinite Programming}
}

Keywords: Graph Partitioning, Max-k-Cut, Semidefinite Programming
Collection: 1st Symposium on Simplicity in Algorithms (SOSA 2018)
Issue Date: 2018
Date of publication: 05.01.2018

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