# Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 55 references that are in the map.
- First posted on arXiv 7 Jan 2023.

## Builds on (most cited first, 19 of 19)

- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding](https://mlsanity.com/paper/1711.01323/) (2017)
- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics](https://mlsanity.com/paper/1804.02530/) (2018)
- [Approximation Schemes for Clustering with Outliers](https://mlsanity.com/paper/1707.04295/) (2017)
- [The Non-Uniform k-Center Problem](https://mlsanity.com/paper/1605.03692/) (2016)
- [Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially](https://mlsanity.com/paper/1802.09205/) (2018)
- [A Practical Algorithm for Distributed Clustering and Outlier Detection](https://mlsanity.com/paper/1805.09495/) (2018)
- [Distributed k-Clustering for Data with Heavy Noise](https://mlsanity.com/paper/1810.07852/) (2018)
- [Fast Noise Removal for k-Means Clustering](https://mlsanity.com/paper/2003.02433/) (2020)
- [Distributed Partial Clustering](https://mlsanity.com/paper/1703.01539/) (2017)
- [k-Center Clustering with Outliers in the Sliding-Window Model](https://mlsanity.com/paper/2109.11853/) (2021)
- [A Composable Coreset for k-Center in Doubling Metrics](https://mlsanity.com/paper/1902.01896/) (2019)
- [Approximation Algorithms for Continuous Clustering and Facility Location Problems](https://mlsanity.com/paper/2206.15105/) (2022)

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

- [Efficient Training of Deep Networks using Guided Spectral Data Selection: A Step Toward Learning What You Need](https://mlsanity.com/paper/2507.04269/) (2025)

## Abstract (arXiv)

In this paper, we study the problem of em k-center clustering with outliers. The problem has many important applications in real world, but the presence of outliers can significantly increase the computational complexity. Though a number of methods have been developed in the past decades, it is still quite challenging to design quality guaranteed algorithm with low complexity for this problem. Our idea is inspired by the greedy method, Gonzalez's algorithm, that was developed for solving the ordinary k-center clustering problem. Based on some novel observations, we show that a simple randomized version of this greedy strategy actually can handle outliers efficiently. We further show that this randomized greedy approach also yields small coreset for the problem in doubling metrics (even if the doubling dimension is not given), which can greatly reduce the computational complexity. Moreover, together with the partial clustering framework proposed in arXiv:1703.01539 , we prove that our coreset method can be applied to distributed data with a low communication complexity. The experimental results suggest that our algorithms can achieve near optimal solutions and yield lower complexities comparing with the existing methods.