Fetching the paper…
Reading the bibliography…
We study local search algorithms for metric instances of facility location problems: the uncapacitated facility location problem (UFL), as well as uncapacitated versions of the $k$-median, $k$-center and $k$-means problems.
Heuristics for the fixed cost median problem
Dorit S. Hochbaum · 1982
Earlier work this paper cites.
Least squares quantization in PCM
S.P. Lloyd · 1982
Earlier work this paper cites.
Clustering to minimize the maximum intercluster distance
Teofilo F. Gonzalez · 1985
Earlier work this paper cites.
A unified approach to approximation algorithms for bottleneck problems
Dorit S. Hochbaum and David B. Shmoys · 1986
Earlier work this paper cites.
Approximation algorithms for facility location problems
David B. Shmoys, Éva Tardos, and Karen I. Aardal · 1997
Earlier work this paper cites.
Improved approximation algorithms for uncapacitated facility location
Fabián A. Chudak · 1998
Earlier work this paper cites.
Analysis of a local search heuristic for facility location problems
Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman · 1998
Earlier work this paper cites.
A constant-factor approximation algorithm for the
Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys · 1999
Earlier work this paper cites.
Greedy strikes back: improved facility location algorithms
Sudipto Guha and Samir Khuller · 1999
Cited alongside, same era.
Approximation algorithms for metric facility location and
Kamal Jain and Vijay Vazirani · 2001
Cited alongside, same era.
A greedy facility location algorithm analyzed using dual fitting
Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay Vazirani · 2001
Cited alongside, same era.
A new greedy approach for facility location problems
Kamal Jain, Mohammad Mahdian, and Amin Saberi · 2002
Cited alongside, same era.
Improved approximation algorithms for metric facility location problems
Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang · 2002
Cited alongside, same era.
An improved approximation algorithm for the metric uncapacitated facility location problem
Group strategyproof mechanisms via primal-dual algorithms
Martin Pál and Éva Tardos · 2003
Later among the works it cites.
Local search heuristics for
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit · 2004
Later among the works it cites.
A local search approximation algorithm for
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu · 2004
Later among the works it cites.
Local Search Heuristics for Facility Location Problems
Vinayaka Pandit · 2004
Later among the works it cites.
Improved combinatorial algorithms for facility location problems
Moses Charikar and Sudipto Guha · 2005
Later among the works it cites.
Price of anarchy, locality gap, and a network service provider game
Nikhil Devanur, Naveen Garg, Rohit Khandekar, Vinayaka Pandit, Amin Saberi, and Vijay Vazirani · 2005
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Maxim Sviridenko · 2002
Cited alongside, same era.
Lagrangian relaxation for the
Aaron Archer, Ranjithkumar Rajagopalan, and David B. Shmoys · 2003
Cited alongside, same era.
Improved approximation algorithms for the uncapacitated facility location problem
Fabián A. Chudak and David B. Shmoys · 2003
Cited alongside, same era.
A simple linear time
Amit Kumar, Yogish Sabharwal, and Sandeep Sen
Cited in the paper.
An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
Jaroslaw Byrka · 2007
Later among the works it cites.