Constant Approximation for Capacitated $k$-Median with $(1 + \epsilon)$-Capacity Violation

ϵ \epsilon -approximations with minimum packing constraint violation (extended abstract)

J. Lin and J. S. Vitter · 1992

Earlier work this paper cites.

Approximation algorithms for facility location problems (extended abstract)

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

Earlier work this paper cites.

Improved combinatorial algorithms for the facility location and k-median problems

M. Charikar and S. Guha · 1999

Earlier work this paper cites.

A constant-factor approximation algorithm for the k-median problem (extended abstract)

M. Charikar, S. Guha, É. Tardos, and D. B. Shmoys · 1999

Earlier work this paper cites.

Strengthening integrality gaps for capacitated network design and covering problems

Robert D. Carr, Lisa K. Fleischer, Vitus J. Leung, and Cynthia A. Phillips · 2000

Earlier work this paper cites.

Approximation Algorithms for Facility Location Problems

Sudipto Guha · 2000

Earlier work this paper cites.

Local search heuristic for k-median and facility location problems

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

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

Cited alongside, same era.

A new greedy approach for facility location problems

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

Cited alongside, same era.

Approximating k-median with non-uniform capacities

Julia Chuzhoy and Yuval Rabani · 2005

Cited alongside, same era.

Approximating k-median via pseudo-approximation

Shi Li and Ola Svensson · 2013

Cited alongside, same era.

LP-based algorithms for capacitated facility location

Hyung-Chan An, Mohit Singh, and Ola Svensson · 2014

Cited alongside, same era.

An improved approximation algorithm for the hard uniform capacitated k-median problem

Shanfei Li · 2014

Cited alongside, same era.

Approximation algorithms for hard capacitated k-facility location problems

Karen Aardal, Pieter L. van den Berg, Dion Gijswijt, and Shanfei Li · 2015

Later among the works it cites.

Bi-factor approximation algorithms for hard capacitated k-median problems

Jarosław Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase · 2015

Later among the works it cites.

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

Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh · 2015

Later among the works it cites.

An approximation algorithm for uniform capacitated k k -median problem with 1 + ϵ 1+\epsilon capacity violation, 2015

Original

Jarosław Byrka, Bartosz Rybicki, and Sumedha Uniyal · 2015

Later among the works it cites.

On uniform capacitated k k -median beyond the natural LP relaxation

Shi Li · 2015

Later among the works it cites.