Clustering What Matters in Constrained Settings (Improved Outlier to Outlier-Free Reductions)
Clustering What Matters in Constrained Settings (Improved Outlier to Outlier-Free Reductions)
Abstract Constrained clustering problems generalize classical clustering formulations, e.g., k-median, k-means, by imposing additional constraints on the feasibility of a clustering. There has been significant recent progress in obtaining approximation algorithms for these problems, both in the metric and the Euclidean settings. However, the outlier version of these problems, where …