Constant factor FPT approximation for capacitated k-median

ε \varepsilon -approximations with minimum packing constraint violation (extended abstract)

J.-H. Lin and J. S. Vitter · 1992

Earlier work this paper cites.

Rounding via trees: Deterministic approximation algorithms for group steiner trees and k -median

M. Charikar, C. Chekuri, A. Goel, and S. Guha · 1998

Earlier work this paper cites.

Approximating a finite metric by a small number of tree metrics

M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. A. Plotkin · 1998

Earlier work this paper cites.

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.

Analysis of a local search heuristic for facility location problems

M. R. Korupolu, C. G. Plaxton, and R. Rajaraman · 2000

Earlier work this paper cites.

A tight bound on approximating arbitrary metrics by tree metrics

J. Fakcharoenphol, S. Rao, and K. Talwar · 2003

Earlier work this paper cites.

Combinatorial Optimization - Polyhedra and Efficiency

A. Schrijver · 2003

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

Cited alongside, same era.

Lp rounding for k-centers with non-uniform hard capacities

M. Cygan, M. Hajiaghayi, and S. Khuller · 2012

Cited alongside, same era.

Planar f-deletion: Approximation, kernelization and optimal fpt algorithms

F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh · 2012

Cited alongside, same era.

Approximating k-median via pseudo-approximation

S. Li and O. Svensson · 2013

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

Cited alongside, same era.

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

J. Byrka, B. Rybicki, and S. Uniyal · 2016

Later among the works it cites.

Constant approximation for capacitated k-median with ( 1 + ϵ ) (1+\epsilon) -capacity violation

H. G. Demirci and S. Li · 2016

Later among the works it cites.

Approximating capacitated k k -median with ( 1 + ϵ ) ​ k (1+\epsilon)k open facilities

S. Li · 2016

Later among the works it cites.

From gap-eth to fpt-inapproximability: Clique, dominating set, and more

P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, and L. Trevisan · 2017

Later among the works it cites.

Partitioning a graph into small pieces with applications to path transversal

E. Lee · 2017

Later among the works it cites.

An fpt algorithm beating 2-approximation for k-cut