Approximate clustering without the approximation

Maria Florina Balcan, Avrim Blum, Anupam Gupta

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


Approximation algorithms for clustering points in metric spaces is a flourishing area of research, with much research effort spent on getting a better understanding of the approximation guarantees possible for many objective functions such as k-median, k-means, and min-sum clustering. This quest for better approximation algorithms is further fueled by the implicit hope that these better approximations also yield more accurate clusterings. E.g., for many problems such as clustering proteins by function, or clustering images by subject, there is some unknown correct "target" clustering and the implicit hope is that approximately optimizing these objective functions will in fact produce a clustering that is close pointwise to the truth. In this paper, we show that if we make this implicit assumption explicit - that is, if we assume that any c-approximation to the given clustering objective Φ is ∈-close to the target - then we can produce clusterings that are O(∈)-close to the target, even for values c for which obtaining a c-approximation is NP-hard. In particular, for k-median and k-means objectives, we show that we can achieve this guarantee for any constant c > 1, and for the min-sum objective we can do this for any constant c > 2. Our results also highlight a surprising conceptual difference between assuming that the optimal solution to, say, the k-median objective is ∈-close to the target, and assuming that any approximately optimal solution is ∈-close to the target, even for approximation factor say c = 1.01. In the former case, the problem of finding a solution that is O(∈)-close to the target remains computationally hard, and yet for the latter we have an efficient algorithm.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)9780898716801
StatePublished - 2009
Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
Duration: Jan 4 2009Jan 6 2009

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityNew York, NY

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Approximate clustering without the approximation'. Together they form a unique fingerprint.

Cite this