A bi-criteria approximation algorithm for κ-Means

Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

We consider the classical κ-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output βκ > k clusters, and must produce a clustering with cost at most α times the to the cost of the optimal set of k clusters. We argue that this approach is natural in many settings, for which the exact number of clusters is a priori unknown, or unimportant up to a constant factor. We give new bi-criteria approximation algorithms, based on linear programming and local search, respectively, which attain a guarantee α(β) depending on the number κ of clusters that may be opened. Our guarantee α(β) is always at most 9+ϵ and improves rapidly with β (for example: α(2) < 2.59, and α(3) < 1.4). Moreover, our algorithms have only polynomial dependence on the dimension of the input data, and so are applicable in high-dimensional settings.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume60
ISBN (Electronic)9783959770187
DOIs
StatePublished - Sep 1 2016
Event19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 - Paris, France
Duration: Sep 7 2016Sep 9 2016

Other

Other19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016
CountryFrance
CityParis
Period9/7/169/9/16

Keywords

  • Bicriteria approximation algorithms
  • Linear programming
  • Local search
  • κ-means clustering

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'A bi-criteria approximation algorithm for κ-Means'. Together they form a unique fingerprint.

Cite this