An approximation algorithm for Uniform Capacitated k-Median problem with 1 + {\epsilon} capacity violation

Built on

A constant-factor approximation algorithm for the k-median problem
M. Charikar, S. Guha, É. Tardos, and D. B. Shmoys · 1999
Earlier work this paper cites.
An improved approximation algorithm for the metric uncapacitated facility location problem
Original
M. Sviridenko · 2002
Earlier work this paper cites.
Local search heuristics for 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.
Approximating k-median with non-uniform capacities
J. Chuzhoy and Y. Rabani · 2005
Earlier work this paper cites.

Dependent rounding and its applications to approximation algorithms
R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan · 2006
Cited alongside, same era.
Approximating k-median via pseudo-approximation
S. Li and O. Svensson · 2013
Cited alongside, same era.
LP-based algorithms for capacitated facility location
H.-C. An, M. Singh, and O. Svensson · 2014
Cited alongside, same era.
Approximation algorithms for hard capacitated k-facility location problems
K. Aardal, P. L. van den Berg, D. Gijswijt, and S. Li · 2015
Cited alongside, same era.

Bi-factor approximation algorithms for hard capacitated k-median problems
J. Byrka, K. Fleszar, B. Rybicki, and J. Spoerhase · 2015
Closest in time.
An improved approximation for k-median, and positive correlation in budgeted optimization
J. Byrka, T. Pensyl, B. Rybicki, A. Srinivasan, and K. Trinh · 2015
Closest in time.
On uniform capacitated k-median beyond the natural lp relaxation
S. Li · 2015
Closest in time.
Approximating capacitated k k -median with ( 1 + ϵ ) k (1+\epsilon)k open facilities
S. Li · 2016
Closest in time.