|
Abstract : |
Abstract. MAX CUT is the problem of partitioning the vertices of a graph into two sets, maximizing the number of edges joining these sets. Goemans and Williamson gave an algorithm that approximates MAX CUT within a ratio of 0.87856. Their algorithm first uses a semidefinite programming relaxation of MAX CUT that embeds the vertices of the graph on the surface of an n dimensional sphere, and then cuts the sphere in two at random. In this survey we shall review several variations of this algorithm which o#er improved approximation ratios for some special families of instances of MAX CUT, as well as for problems related to MAX CUT. 1, |
