TY - JOUR
T1 - Clustering improves the Goemans–Williamson approximation for the max-cut problem
AU - Rodriguez-Fernandez, Angel E.
AU - Gonzalez-Torres, Bernardo
AU - Menchaca-Mendez, Ricardo
AU - Stadler, Peter F.
N1 - Publisher Copyright:
© 2020 by the authors. Licensee MDPI, Basel, Switzerland.
PY - 2020/9
Y1 - 2020/9
N2 - 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.
AB - 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.
KW - Algorithms
KW - Approximation
KW - Clustering
KW - Max-Cut
KW - Semidefinite programming
UR - http://www.scopus.com/inward/record.url?scp=85096046847&partnerID=8YFLogxK
U2 - 10.3390/computation8030075
DO - 10.3390/computation8030075
M3 - Artículo
AN - SCOPUS:85096046847
SN - 2079-3197
VL - 8
SP - 1
EP - 12
JO - Computation
JF - Computation
IS - 3
M1 - 75
ER -