Fetching the paper…
Reading the bibliography…
In this paper, we consider the fault-tolerant $k$-median problem and give the \emph{first} constant factor approximation algorithm for it.
Covering problems
A. Kolen and A. Tamir · 1990
Earlier work this paper cites.
e-approximations with minimum packing constraint violation (extended abstract)
J. H. Lin and J. S. Vitter · 1992
Earlier work this paper cites.
Approximation algorithms for geometric median problems
J.H. Lin and J.S. Vitter · 1992
Earlier work this paper cites.
An o ( p n 2 pn^{2} ) algorithm for the p-median and related problems on tree graphs
A. Tamir · 1996
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.
On approximating arbitrary metrices by tree metrics
Y. Bartal · 1998
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.
The p-neighbor k-center problem
S. Chaudhuri, N. Garg, and R. Ravi · 1998
Earlier work this paper cites.
Improved approximation algorithms for uncapacitated facility location
F. A. Chudak · 1998
Earlier work this paper cites.
Greedy strikes back: improved facility location algorithms
S. Guha and S. Khuller · 1998
Earlier work this paper cites.
A 3-approximation algorithm for the k-level uncapacitated facility location problem
K. Aardal, F. A. Chudak, and D. B. Shmoys · 1999
Earlier work this paper cites.
Primal-dual approximation algorithms for metric facility location and k-median problems
K. Jain and V. V. Vazirani · 1999
Earlier work this paper cites.
Strengthening integrality gaps for capacitated network design and covering problems
R. D. Carr, L. K. Fleischer, V. J. Leung, and C. A. Phillips · 2000
Earlier work this paper cites.
Fault tolerant k-center problems
S. Khuller, R. Pless, and Y. Sussmann · 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
Cited alongside, same era.
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.
Facility location with nonuniform hard capacities
M. Pal, T. Tardos, and T. Wexler · 2001
Cited alongside, same era.
A constant-factor approximation algorithm for the k-median problem
M. Charikar, S. Guha, É. Tardos, and D.B. Shmoys · 2002
Cited alongside, same era.
Lagrangian relaxation for the k-median problem: new insights and continuity properties
A. Archer, R. Rajagopalan, and D. B. Shmoys · 2003
Cited alongside, same era.
A tight bound on approximating arbitrary metrics by tree metrics
Approximating k-median with non-uniform capacities
J. Chuzhoy and Y. Rabani · 2005
Later among the works it cites.
A plant location guide for the unsure
B. M. Anthony, V. Goyal, A. Gupta, and V. Nagarajan · 2008
Later among the works it cites.
Fault-tolerant facility location
C. Swamy and D. B. Shmoys · 2008
Later among the works it cites.
A constant factor approximation algorithm for generalized min-sum set cover
N. Bansal, A. Gupta, and R. Krishnaswamy · 2010
Later among the works it cites.
Fault-tolerant facility location: a randomized dependent lp-rounding algorithm
J. Byrka, A. Srinivasan, and C. Swamy · 2010
Later among the works it cites.
Budgeted red-blue median and its generalizations
M. T. Hajiaghayi, R. Khandekar, and G. Kortsarz · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
J. Fakcharoenphol, S. Rao, and K. Talwar · 2003
Cited alongside, same era.
A constant factor approximation algorithm for the fault-tolerant facility location problem
S. Guha, A. Meyerson, and K. Munagala · 2003
Cited alongside, same era.
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
Cited alongside, same era.
An approximation algorithm for the fault tolerant metric facility location problem
J. Kamal and V. V. Vazirani · 2003
Cited alongside, same era.
Universal facility location
M. Mahdian and M. Pál · 2003
Cited alongside, same era.
Combinatorial Optimization : Polyhedra and Efficiency
A. Schrijver · 2003
Cited alongside, same era.
Improved approximation algorithms for the uncapacitated facility location problem
F. A. Chudak and D. B. Shmoys · 2004
Cited alongside, same era.
Lower-bounded facility location
Z. Svitkina · 2010
Later among the works it cites.
The matroid median problem
R. Krishnaswamy, A. Kumar, V. Nagarajan, Y. Sabharwal, and B. Saha · 2011
Later among the works it cites.
Generalized machine activation problems
J. Li and S. Khuller · 2011
Later among the works it cites.
A 1.488 approximation algorithm for the uncapacitated facility location problem
S. Li · 2011
Later among the works it cites.
A dependent LP-rounding approach for the k-median problem
M. Charkar and S. Li · 2012
Later among the works it cites.
Constant factor approximation algorithm for the knapsack median problem
A. Kumar · 2012
Later among the works it cites.
LP-rounding algorithms for the fault-tolerant facility placement problem
L. Yan and M. Chrobak · 2012
Later among the works it cites.
Approximating k-median via pseudo-approximation
Shi Li and Ola Svensson · 2013
Closest in time.