Approximation Scheme for Weighted Metric Clustering via Sherali-Adams

Motivated by applications to classification problems on metric data, we study Weighted Metric Clustering problem: given a metric d over n points, the goal is to find a k-partition of these points into clusters C₁, ..., C_k, while minimizing (Equation presented), where A is a k × k symmetric matrix with non-negative entries. Specific choices of A lead to Weighted Metric Clustering capturing well-studied graph partitioning problems in metric spaces, such as Min-Uncut, Min-k-Sum, Min-k-Cut, and more. Our main result is that Weighted Metric Clustering admits a polynomial-time approximation scheme (PTAS). Our algorithm handles all the above problems using the Sherali-Adams linear programming relaxation. This subsumes several prior works, unifies many of the techniques for various metric clustering objectives, and yields a PTAS for several new problems, including metric clustering on manifolds and a new family of hierarchical clustering objectives. Our experiments on the hierarchical clustering objective show that it better captures the ground-truth structural information compared to the popular Dasgupta's objective.