Improved Approximation Algorithms for the Uncapacitated Facility Location Problem

By Fabián A. Chudak, David B. Shmoys. SIAM journal on computing (Print), 2003

328 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

A new greedy approach for facility location problems (2002, methodology): “Shmoys.”
The Design of Approximation Algorithms (2011, background): “The Design of Approximation Algorithms David P. Williamson and David B. Shmoys Frontmatter More information”
On the placement of Web server replicas (2001, background): “However, the worst-case performance bound for the capacitated variants are considerably worse than for non-capacitated versions [ 9 ], [7].”
A 1.488 approximation algorithm for the uncapacitated facility location problem (2011, background): “After that, a large number of constant approximation algorithms have been proposed([4], [9], [3], [7], [8], [11]).”
Local search heuristic for k-median and facility location problems (2001, background): “Thiswas furtherimprovedto(1+2!e)byChudak[2]andfnally to1.”
Local Search Heuristics for k-Median and Facility Location Problems (2004, background): “Similar ideas were used by Chudak and Shmoys [7] to obtain a 3 approximation algorithm for ∞-CFL when the capacities are uniform.”