Clustering improves the Goemans–Williamson approximation for the max-cut problem

Angel E. Rodriguez-Fernandez, Bernardo Gonzalez-Torres, Ricardo Menchaca-Mendez, Peter F. Stadler

Research output: Contribution to journalArticlepeer-review

Abstract

MAX-CUT is one of the well-studied NP-hard combinatorial optimization problems. It can be formulated as an Integer Quadratic Programming problem and admits a simple relaxation obtained by replacing the integer “spin” variables xi by unitary vectors ⃗vi . The Goemans–Williamson rounding algorithm assigns the solution vectors of the relaxed quadratic program to a corresponding integer spin depending on the sign of the scalar product ⃗vi ·⃗r with a random vector⃗r. Here, we investigate whether better graph cuts can be obtained by instead using a more sophisticated clustering algorithm. We answer this question affirmatively. Different initializations of k-means and k-medoids clustering produce better cuts for the graph instances of the most well known benchmark for MAX-CUT. In particular, we found a strong correlation of cluster quality and cut weights during the evolution of the clustering algorithms. Finally, since in general the maximal cut weight of a graph is not known beforehand, we derived instance-specific lower bounds for the approximation ratio, which give information of how close a solution is to the global optima for a particular instance. For the graphs in our benchmark, the instance specific lower bounds significantly exceed the Goemans–Williamson guarantee.

Original languageEnglish
Article number75
Pages (from-to)1-12
Number of pages12
JournalComputation
Volume8
Issue number3
DOIs
StatePublished - Sep 2020

Keywords

  • Algorithms
  • Approximation
  • Clustering
  • Max-Cut
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'Clustering improves the Goemans–Williamson approximation for the max-cut problem'. Together they form a unique fingerprint.

Cite this