Approximation algorithms for facility location problems

By Sudipto Guha. 2000

369 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/a360d5d63826970e1030d5dce2d96c8b2826712e

How researchers see this paper

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

Citations in the corpus

Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP (2002, background): “The dashed line shows the following lower bound, which can be proved easily by adapting the proof of Guha and Khuller [1999] for hardness of the facility location problem.”
Provisioning a virtual private network: a network design problem for multicommodity flow (2001, methodology): “We provide a signiﬁcantly improved constant-factor approximation algorithm for the Connected Facility Location problem, adapting a rounding technique of Shmoys, Tardos, and Aardal [22].”
A review of hierarchical facility location models (2007, background): “Shmoys, Tardos, Aardal 1997 [76] S – C F Approximation algorithms for two level systems”
Local Search Heuristics for k-Median and Facility Location Problems (2004, methodology): “A different approach to facility location was employed by Shmoys, Tardos, and Aardal [20] and Charikar et al. [5].”
Privacy preserving clustering with constraints (2018, methodology): “Lemma 33.”
An Algorithm for Online K-Means Clustering (2014, background): “These problems are well-studied both from computational and theoretic viewpoints (a book [13] and a survey [24] provide the background on some of the aspects in this area).”
Online facility location (2001, background): “The problem is MAX-SNP Hard and the first constant approximation was given by Shmoys, Tardos, and Aardal [13]; this was later improved to by Charikar and Guha [2] and to by Sviridenko [14].”
Primal-dual approximation algorithms for metric facility location and k-median problems (1999, methodology): “Part of the problem is that all LPrelaxations known for this problem have unbounded integrality gap (see [32]).”
Stochastic Optimization for Natural Disaster Asset Prepositioning (2010, background): “…facilities for ﬁre stations or ambulances under the paradigm of set covering problems: a demand is covered if there exists at least one available unit within a speciﬁed distance from its location (see, e.g., Cabot et al. 1970, Church and ReVelle 1974, Shmoys et al. 1997, Tonegas et al. 1971).”
Algorithms for facility location problems with outliers (2001, background): “All of these optimization problems are NPhard, and polynomial time approximation algorithms have been studied (see [17, 4, 5, 6, 31, 19, 13, 15, 21, 23]).”
A constant-factor approximation algorithm for the k-median problem (extended abstract) (1999, background): “Charikar & Guha give a polynomial-time algorithm that finds a solution of cost at most 16 times the true optimal cost, but allows centers to be assigned at most 4U locations.”
Clustering Data Streams: Theory and Practice (2003, background): “There is abundant literature on these, books [45], [62], [55], provable algorithms [41], [49], [54], [53], [71], [31], [16], [15], [6], [52], [47], [14], [59], [7], [46], the running time of provable clustering heuristics [21], [10], [42], [34], [73], [60], and special metric spaces [6], [52],…”
The Design of Approximation Algorithms (2011, background): “5 is due to Chudak and Shmoys [77], building on earlier work of Shmoys, Tardos, and Aardal [264].”
Analysis of a local search heuristic for facility location problems (2000, methodology): “Using the reduction of [24] that is based on solving a special case of the generalized assignment problem [23], the above results for the capacitated problems with splittable demands imply constant-factor approximation bounds for the capacitated problems with unsplittable demands (CKMU and CFLU) ass”
Local search heuristic for k-median and facility location problems (2001, methodology): “Adiferentapproahtofailityloationwasemployed byShmoys,TardosandAardal[1O]andCharikar,Guha, ShmoysandTardos[11].”
A new greedy approach for facility location problems (2002, background): “In the last decade this problem was studied extensively from the perspective of approximation algorithms [2, 4, 6, 7, 8, 13, 18, 20, 28, 30].”