# Constant approximation for k-median and k-means with outliers via iterative rounding

```@article{Krishnaswamy2018ConstantAF,
title={Constant approximation for k-median and k-means with outliers via iterative rounding},
author={Ravishankar Krishnaswamy and Shi Li and Sai Sandeep},
journal={Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing},
year={2018}
}```
• Published 2018
• Computer Science, Mathematics
• Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
In this paper, we present a new iterative rounding framework for many clustering problems. Using this, we obtain an (α1 + є ≤ 7.081 + є)-approximation algorithm for k-median with outliers, greatly improving upon the large implicit constant approximation ratio of Chen. For k-means with outliers, we give an (α2+є ≤ 53.002 + є)-approximation, which is the first O(1)-approximation for this problem. The iterative algorithm framework is very versatile; we show how it can be used to give α1- and (α1… Expand
Structural Iterative Rounding for Generalized k-Median Problems
• Computer Science, Mathematics
• ICALP
• 2021
Improved approximation algorithms for generalized \$k-median with outliers and knapsack median are given, allowing richer constraint sets in the iterative rounding and taking advantage of the structure of the resulting extreme points. Expand
Greedy Sampling for Approximate Clustering in the Presence of Outliers
This work shows that for k-means and k-center clustering, simple modifications to the well-studied greedy algorithms result in nearly identical guarantees, while additionally being robust to outliers. Expand
Improved Algorithms for Clustering with Outliers
• Computer Science, Mathematics
• ISAAC
• 2019
This paper gave the first PTAS for the k-median problem with outliers in Euclidean space R^d for possibly high m and d, and introduced a (6+epsilon)-approximation algorithm for general metric space with running time O(n(beta (1/ep silon)(k+m))^k) for some constant beta>1. Expand
Outliers Detection Is Not So Hard: Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques
• Computer Science, Mathematics
• ArXiv
• 2020
A new technique to analyze the approximation ratio of local search algorithms for k-median/k-means problems by introducing an adapted cluster that can capture useful information about outliers in the local and the global optimal solution. Expand
Robust k-means++
• Computer Science, Physics
• UAI
• 2020
This work shows that using a mixture of D and uniform sampling, one can pick O(k/δ) candidate centers with the following guarantee: they contain some k centers that give O(1)-approximation to the optimal robust k-means solution while discarding at most δn more points than the outliers discarded by the optimal solution. Expand
An Improved Approximation Algorithm for the k-Means Problem with Penalties
• Computer Science
• FAW
• 2019
The clustering problem has been paid lots of attention in various fields of compute science. However, in many applications, the existence of noisy data poses a big challenge for the clusteringExpand
Improved Approximation Algorithms for Individually Fair Clustering
• Computer Science
• ArXiv
• 2021
This work extends the framework of [Charikar et al., 2002, Swamy, 2016] and devise a 16-approximation algorithm for the facility location with lp-norm cost under matroid constraint which might be of an independent interest and suggests a reduction from an individually fair clustering to a clustering with a group fairness requirement proposed by Kleindessner et al. Expand
On Sampling Based Algorithms for k-Means
• Computer Science
• FSTTCS
• 2020
Making use of a constant factor solution for the (classical or unconstrained) k-means problem, the results of Bhattacharya et al. are generalised and a constant pass, polylog-space streaming PTAS for either of the two problems is designed. Expand
Fault Tolerant Clustering with Outliers
• Mathematics, Computer Science
• WAOA
• 2019
This work essentially reduces the Fault Tolerant Clustering with Outliers problem, to the corresponding (non Fault Tolerance) Clustered with outlier problem, for which constant approximations are known, and shows that it is bounded by O(1) for the k-center objective, whereas it is O(f) for k-median and sum of radii objectives. Expand
Is Simple Uniform Sampling Efficient for Center-Based Clustering With Outliers: When and Why?
• Computer Science
• ArXiv
• 2021
This is the first work that systematically studies the effectiveness of uniform sampling from both theoretical and experimental aspects, and introduces a “significance” criterion and proves that the performance of the framework depends on the significance degree of the given instance. Expand
{"ft_lang_label":"__label__en","ft_lang_prob":0.83696336,"math_prob":0.74280906,"size":8782,"snap":"2021-31-2021-39","text_gpt3_token_len":1928,"char_repetition_ratio":0.18272956,"word_repetition_ratio":0.05352987,"special_character_ratio":0.20109315,"punctuation_ratio":0.06517169,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9914538,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-19T07:24:38Z\",\"WARC-Record-ID\":\"<urn:uuid:80a91488-1a39-4fd5-8701-f23cc76e67f6>\",\"Content-Length\":\"439974\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:21e8f395-d87e-47a1-90ea-3ec3bd462f23>\",\"WARC-Concurrent-To\":\"<urn:uuid:67cedb3e-a53f-416b-92d7-c16a770ba15b>\",\"WARC-IP-Address\":\"13.32.204.45\",\"WARC-Target-URI\":\"https://www.semanticscholar.org/paper/Constant-approximation-for-k-median-and-k-means-via-Krishnaswamy-Li/160603fd5e58c82deaa3e8557a2a4dd329c70272\",\"WARC-Payload-Digest\":\"sha1:QW34AXYBECBBTK4IX4TCNTERWPQOBDEN\",\"WARC-Block-Digest\":\"sha1:6TI4RHVD2KJYWWUJU66O3SFQOLSOWEIS\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780056752.16_warc_CC-MAIN-20210919065755-20210919095755-00626.warc.gz\"}"}