betaFeedback

WorksComputer Science

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Abstract

Clustering is a classic topic in optimization with kk-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algorithm for kk-means with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9+ε9+ε, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of kk-means and (2) to satisfy the hard constraint that at most kk clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.3576.357-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of kk-means where the underlying metric is not required to be Euclidean and for kk-median in Euclidean metrics.

Paper details

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

views · 5

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…