Skip to main navigation Skip to search Skip to main content

Constant approximation for k-Median and k-Means with outliers via iterative rounding

  • Ravishankar Krishnaswamy
  • , Shi Li
  • , Sai Sandeep
  • Microsoft USA

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

91 Scopus citations

Abstract

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 +)-approximation algorithms for matroid and knapsack median problems respectively, improving upon the previous best approximations ratios of 8 due to Swamy and 17.46 due to Byrka et al. The natural LP relaxation for the k-median/k-means with outliers problem has an unbounded integrality gap. In spite of this negative result, our iterative rounding framework shows that we can round an LP solution to an almost-integral solution of small cost, in which we have at most two fractionally open facilities. Thus, the LP integrality gap arises due to the gap between almost-integral and fully-integral solutions. Then, using a pre-processing procedure, we show how to convert an almost-integral solution to a fully-integral solution losing only a constant-factor in the approximation ratio. By further using a sparsification technique, the additive factor loss incurred by the conversion can be reduced to any > 0.

Original languageEnglish
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
EditorsMonika Henzinger, David Kempe, Ilias Diakonikolas
PublisherAssociation for Computing Machinery
Pages339-352
Number of pages14
ISBN (Electronic)9781450355599
DOIs
StatePublished - Jun 20 2018
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: Jun 25 2018 → Jun 29 2018

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference50th Annual ACM Symposium on Theory of Computing, STOC 2018
Country/TerritoryUnited States
CityLos Angeles
Period06/25/18 → 06/29/18

Keywords

  • Approximation algorithms
  • Iterative rounding
  • K-means
  • K-median
  • Outliers

Fingerprint

Dive into the research topics of 'Constant approximation for k-Median and k-Means with outliers via iterative rounding'. Together they form a unique fingerprint.

Cite this