

Author: Fernandez de la Vega W. Kenyon C.
Publisher: Academic Press
ISSN: 0022-0000
Source: Journal of Computer and System Sciences, Vol.63, Iss.4, 2001-12, pp. : 531-541
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
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 is NP-complete but has a polynomial time randomized approximation scheme.
Related content




Lagrangian Smoothing Heuristics for Max-Cut
Journal of Heuristics, Vol. 11, Iss. 5-6, 2005-12 ,pp. :






Parallel Algorithms and Applications, Vol. 17, Iss. 3, 2001-01 ,pp. :