A Randomized Approximation Scheme for Metric MAX-CUT

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.

Authors

• Wenceslas Fernandez de la Vega
• Claire Mathieu

Keywords

• Polynomials
• Partitioning algorithms
• Clustering algorithms
• Approximation algorithms
• Web pages
• World Wide Web
• Extraterrestrial measurements
• Algorithm design and analysis
• Space exploration
• Traveling salesman problems
• Estimation Strategy
• Randomized Approximation Scheme
• Points In Space
• Sum Of Distances
• Constant Factor
• Triangle Inequality
• Polynomial-time Algorithm
• Traveling Salesman Problem
• Optimal Cut
• Weighted Graph