Clustering Improves the Goemans-Williamson Approximation for the Max-Cut Problem

MAX-CUTis 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" variablesxiby unitary vectors (nu) over right arrow (i). 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 (nu) over right arrow (i)center dot(r) over right arrow with a random vector (r) over right arrow. 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 ofk-means andk-medoids clustering produce better cuts for the graph instances of the most well known benchmark forMAX-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.