Clustering What Matters: Optimal Approximation for Clustering with Outliers


  • Akanksha Agrawal Indian Institute of Technology Madras
  • Tanmay Inamdar University of Bergen
  • Saket Saurabh The Institute of Mathematical Sciences, HBNI University of Bergen
  • Jie Xue New York University Shanghai



ML: Clustering


Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two numbers k and m, the clustering with outliers aims to exclude m points from X, and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m (i.e., an algorithm with running time of the form f(k, m) * poly(n) for some function f), that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.




How to Cite

Agrawal, A., Inamdar, T., Saurabh, S., & Xue, J. (2023). Clustering What Matters: Optimal Approximation for Clustering with Outliers. Proceedings of the AAAI Conference on Artificial Intelligence, 37(6), 6666-6674.



AAAI Technical Track on Machine Learning I