betaFeedback

WorksComputer Science

A bi-criteria approximation algorithm for kk Means

Abstract

We consider the classical kk-means clustering problem in the setting bi-criteria approximation, in which an algoithm is allowed to output βk>kβk > k clusters, and must produce a clustering with cost at most αα times the to the cost of the optimal set of kk 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 βkβk of clusters that may be opened. Our gurantee α(β)α(β) is always at most 9+ε9 + ε and improves rapidly with ββ (for example: α(2)<2.59α(2)<2.59, and α(3)<1.4α(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.

Paper details

vlnc:W_qrnha7w5
Version
v1 · latest
Published
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…