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

Approximation algorithms for geometric median problems

J. Lin and J. S. Vitter · 1992

Earlier work this paper cites.

Approximation algorithms for facility location problems (extended abstract)

D. B. Shmoys, E. Tardos, and K. Aardal · 1997

Earlier work this paper cites.

On approximate geometric k-clustering

J. Matoušek · 2000

Earlier work this paper cites.

Approximation algorithms for metric facility location and k -median problems using the primal-dual schema and lagrangian relaxation

K. Jain and V. V. Vazirani · 2001

Earlier work this paper cites.

Approximation Algorithms

V. V. Vazirani · 2001

Earlier work this paper cites.

A new greedy approach for facility location problems

K. Jain, M. Mahdian, and A. Saberi · 2002

Earlier work this paper cites.

Lagrangian relaxation for the k-median problem: New insights and continuity properties

A. Archer, R. Rajagopalan, and D. B. Shmoys · 2003

Earlier work this paper cites.

Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP

K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani · 2003

Earlier work this paper cites.

Local search heuristics for k k -median and facility location problems

V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit · 2004

Earlier work this paper cites.

Improved approximation algorithms for the uncapacitated facility location problem

F. A. Chudak and D. B. Shmoys · 2004

Earlier work this paper cites.

A local search approximation algorithm for k-means clustering

T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu · 2004

Cited alongside, same era.

Improved combinatorial algorithms for facility location problems

M. Charikar and S. Guha · 2005

Cited alongside, same era.

How slow is the k-means method?

D. Arthur and S. Vassilvitskii · 2006

Cited alongside, same era.

Least squares quantization in PCM

S. Lloyd · 2006

Cited alongside, same era.

K-means++: The advantages of careful seeding

D. Arthur and S. Vassilvitskii · 2007

Cited alongside, same era.

A PTAS for k-means clustering based on weak coresets

D. Feldman, M. Monemizadeh, and C. Sohler · 2007

Cited alongside, same era.

k-means requires exponentially many iterations even in the plane

A. Vattani · 2011

Later among the works it cites.

The Design of Approximation Algorithms

Original

D. P. Williamson and D. B. Shmoys · 2011

Later among the works it cites.

A 1.488 approximation algorithm for the uncapacitated facility location problem

S. Li · 2013

Later among the works it cites.

The effectiveness of Lloyd-type methods for the k-means problem

R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy · 2013

Later among the works it cites.

The hardness of approximation of euclidean k-means

P. Awasthi, M. Charikar, R. Krishnaswamy, and A. K. Sinop · 2015

Later among the works it cites.

An improved approximation for k -median, and positive correlation in budgeted optimization