# Approximation Schemes for Clustering with Outliers

arXiv: https://arxiv.org/abs/1707.04295 · HTML: https://mlsanity.com/paper/1707.04295/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2017.

## Built on by (most cited first, 9 of 9)

- [How to Find a Good Explanation for Clustering?](https://mlsanity.com/paper/2112.06580/) (2021)
- [Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers](https://mlsanity.com/paper/2312.12835/) (2023)
- [Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outliers](https://mlsanity.com/paper/2404.13401/) (2024)
- [Improved Outlier Robust Seeding for k-means](https://mlsanity.com/paper/2309.02710/) (2023)
- [Is Simple Uniform Sampling Effective for Center-Based Clustering with Outliers: When and Why?](https://mlsanity.com/paper/2103.00558/) (2021)
- [Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers](https://mlsanity.com/paper/2301.02814/) (2023)
- [Distributed k-Means with Outliers in General Metrics](https://mlsanity.com/paper/2202.08173/) (2022)
- [Coresets for Clustering Under Stochastic Noise](https://mlsanity.com/paper/2510.23438/) (2025)
- [Simple KNN-Based Outlier Detection Achieves Robust Clustering](https://mlsanity.com/paper/2605.07130/) (2026)

## Abstract (arXiv)

Clustering problems are well-studied in a variety of fields such as data science, operations research, and computer science. Such problems include variants of centre location problems, k-median, and k-means to name a few. In some cases, not all data points need to be clustered; some may be discarded for various reasons. We study clustering problems with outliers. More specifically, we look at Uncapacitated Facility Location (UFL), k-Median, and k-Means. In UFL with outliers, we have to open some centres, discard up to z points of cal X and assign every other point to the nearest open centre, minimizing the total assignment cost plus centre opening costs. In k-Median and k-Means, we have to open up to k centres but there are no opening costs. In k-Means, the cost of assigning j to i is δ2(j,i). We present several results. Our main focus is on cases where δ is a doubling metric or is the shortest path metrics of graphs from a minor-closed family of graphs. For uniform-cost UFL with outliers on such metrics we show that a multiswap simple local search heuristic yields a PTAS. With a bit more work, we extend this to bicriteria approximations for the k-Median and k-Means problems in the same metrics where, for any constant ε > 0, we can find a solution using (1+ε)k centres whose cost is at most a (1+ε)-factor of the optimum and uses at most z outliers. We also show that natural local search heuristics that do not violate the number of clusters and outliers for k-Median (or k-Means) will have unbounded gap even in Euclidean metrics. Furthermore, we show how our analysis can be extended to general metrics for k-Means with outliers to obtain a (25+ε,1+ε) bicriteria.