# Complex Semidefinite Programming and Max-k-Cut

arXiv: https://arxiv.org/abs/1812.10770 · HTML: https://mlsanity.com/paper/1812.10770/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2018.

## Built on by (most cited first, 1 of 1)

- [Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization](https://mlsanity.com/paper/2602.20376/) (2026)

## Abstract (arXiv)

In a second seminal paper on the application of semidefinite programming to graph partitioning problems, Goemans and Williamson showed 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 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 ≥ 4, 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.