A randomized approximation scheme for metric MAX-CUT
W. Fernandez de la Véga, Claire Kenyon · 2002
Metric MAX-CUT is the problem of dividing a set of points in metric space into two parts so as to maximize the sum of the distances between points belonging to distinct parts. We show that metric MAX-CUT has a polynomial time randomized approximation scheme.