2026-07-23T01:23:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6637 2024-03-06T10:38:34Z ddc:004 open_access

A Bi-Criteria Approximation Algorithm for k-Means Makarychev, Konstantin Makarychev, Yury Sviridenko, Maxim Ward, Justin k-means clustering bicriteria approximation algorithms linear programming local search We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha 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 alpha(beta) depending on the number beta*k of clusters that may be opened. Our guarantee alpha(beta) is always at most 9 + epsilon and improves rapidly with beta (for example: alpha(2) < 2.59, and alpha(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konstantin Makarychev and Yury Makarychev and Maxim Sviridenko and Justin Ward 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.14 urn:nbn:de:0030-drops-66370 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.14 eng https://creativecommons.org/licenses/by/3.0/legalcode