×

zbMATH — the first resource for mathematics

A randomized approximation scheme for metric MAX-CUT. (English) Zbl 1006.68164
Summary: 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.

MSC:
68W05 Nonnumerical algorithms
Keywords:
MAX-CUT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arora, S., Polynomial time approximation schemes for Euclidean TSP and other geometric problems, 37th annual symposium on foundations of computer science, (Oct. 1996)
[2] Arora, S., Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, 38th annual symposium on foundations of computer science, (20-22 Oct. 1997), p. 554-563
[3] Arora, S.; Karger, D.; Karpinski, M., Approximation schemes for dense instances of NP-hard problems, Proc. 27th ACM symposium on the theory of computing (STOC), (May 1995), p. 284-293
[4] Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and the hardness of approximation problems, J. assoc. comput. Mach., 45, 501-555, (1998) · Zbl 1065.68570
[5] Boros, E.; Hammer, P., On clustering problems with connected optima in Euclidean spaces, Discrete math., 75, 81-88, (1989) · Zbl 0665.62062
[6] Capoyleas, V.; Rote, G.; Woeginger, G., Geometric clusterings, J. algorithms, 12, 341-356, (1991) · Zbl 0734.68092
[7] Delorme, C.; Poljak, S., Combinatorial properties and the complexity of a MAX-CUT approximation, Eur. J. combin., 14, 313-333, (1993) · Zbl 0780.05040
[8] Delorme, C.; Poljak, S., Laplacian eigenvalues and the maximum cut problem, Math. program., 62, 557-574, (1993) · Zbl 0797.90107
[9] de la Vega, W.F., MAX-CUT has a randomized approximation scheme in dense graphs, Random structures algorithms, 8, 187-198, (1996) · Zbl 0848.90120
[10] de la Vega, W.F.; Karpinski, M., Polynomial time approximation of dense weighted instances of MAX-CUT, electronic colloquium on computational complexity report, (1998) · Zbl 0965.68072
[11] de la Vega, W.F.; Kenyon, C., A randomized approximation scheme for metric MAX-CUT, Proc. of the 39th annual IEEE symposium on foundations of computer science, (November 1998), p. 468-471
[12] Frieze, A.; Kannan, R., Quick approximations to matrices and applications, Combinatorica, 19, 175-220, (1999) · Zbl 0933.68061
[13] Garey, M.; Johnson, D., Computers and intractability, Guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[14] Goemans, M.X.; Williamson, D.P., .878- approximation algorithms for MAX-CUT and MAX-2SAT, Proc. 26th symposium on the theory of computing (STOC), (May 1994), p. 422-431
[15] Goemans, M.X.; Williamson, D.P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. assoc. comput. Mach., 42, 1115-1145, (1995) · Zbl 0885.68088
[16] Goldreich, O.; Goldwasser, S.; Ron, D., Property testing and its connection to learning and approximation, Proceedings of 37th foundations of computer science (FOCS), (November 1996)
[17] Hershberger, H.; Suri, S., Finding tailored partitions, J. algorithms, 12, 431-463, (1991) · Zbl 0726.68077
[18] Hochbaum, D.S., Approximation algorithms for NP-hard problems, (1995), PWS Kent/Boston
[19] Inaba, M.; Katoh, N.; lmai, H., Applications of weighted Voronoi diagrams and randomization of variances-based k-clustering, Proceedings of the 10th ACM symposium on computational geometry, (1994), p. 332-339
[20] Indyk, P., A sublinear-time approximation scheme for clustering in metric spaces, 40th symposium on foundations of computer science, (1999)
[21] Papadimitriou, C.; Yannakakis, M., Optimization, approximation and complexity classes, J. comput. system sci., 43, 425-440, (1991) · Zbl 0765.68036
[22] Poljak, S.; Rendl, F., Solving the MAX-CUT problem using eigenvalues, report, (1991)
[23] Sahni, S.; Gonzalez, T., P-complete approximation problems, J. assoc. comput. Mach., 23, 555-565, (1976) · Zbl 0348.90152
[24] Trevisan, L., When Hamming meets euclid: the approximability of geometric TSP and MST (extended abstract), Proceedings of the twenty-ninth annual symposium on theory of computing, (4-6 May 1997), p. 21-29
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.