2026-07-23T12:53:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8309 2024-03-06T10:30:17Z ddc:004 open_access

Complex Semidefinite Programming and Max-k-Cut Newman, Alantha Graph Partitioning Max-k-Cut Semidefinite Programming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alantha Newman 2018 Is Part Of OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SOSA.2018.13 urn:nbn:de:0030-drops-83098 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.13 eng https://creativecommons.org/licenses/by/3.0/legalcode