Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
Authors:
- Sara AhmadianSASara Ahmadian
- Ashkan Norouzi-FardANAshkan Norouzi-Fard
- Ola SvenssonOSOla Svensson
- Justin WardJWJustin Ward
Top Cited Papers
- 22 October 2019
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 49 (4) , FOCS17-97
Abstract
Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for $k$-means...Keywords
All Related Versions
Funding Information
- H2020 European Research Council (335288)
This publication has 15 references indexed in Scilit:
- k-means Requires Exponentially Many Iterations Even in the PlaneDiscrete & Computational Geometry, 2011
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location ProblemSIAM Journal on Computing, 2010
- Improved Combinatorial Algorithms for Facility Location ProblemsSIAM Journal on Computing, 2005
- A local search approximation algorithm for k-means clusteringComputational Geometry, 2004
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPJournal of the ACM, 2003
- Improved Approximation Algorithms for the Uncapacitated Facility Location ProblemSIAM Journal on Computing, 2003
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxationJournal of the ACM, 2001
- On Approximate Geometric k -ClusteringDiscrete & Computational Geometry, 2000
- Approximation algorithms for geometric median problemsInformation Processing Letters, 1992
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982