Approximation Scheme for Weighted Metric Clustering via Sherali-Adams
Dmitrii Avdiukhin, Vaggos Chatziafratis, Konstantin Makarychev, Grigory Yaroslavtsev
Abstract
Motivated by applications to classification problems on metric data, we study Weighted Metric Clustering problem: given a metric d over n points and a k x k symmetric matrix A with non-negative entries, the goal is to find a k-partition of these points into clusters C1,...,Ck, while minimizing the sum of A[i,j] * d(u,v) over all pairs of clusters Ci and Cj and all pairs of points u from Ci and v from Cj. 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.
BibTeX
@article{Avdiukhin_Chatziafratis_Makarychev_Yaroslavtsev_2024, title={Approximation Scheme for Weighted Metric Clustering via Sherali-Adams}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/28629}, DOI={10.1609/aaai.v38i8.28629}, abstractNote={Motivated by applications to classification problems on metric data, we study Weighted Metric Clustering problem: given a metric d over n points and a k x k symmetric matrix A with non-negative entries, the goal is to find a k-partition of these points into clusters C1,...,Ck, while minimizing the sum of A[i,j] * d(u,v) over all pairs of clusters Ci and Cj and all pairs of points u from Ci and v from Cj. 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.}, number={8}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Avdiukhin, Dmitrii and Chatziafratis, Vaggos and Makarychev, Konstantin and Yaroslavtsev, Grigory}, year={2024}, month={Mar.}, pages={7926-7934} }