Article

An approximation algorithm for the fault tolerant metric facility location problem

Authors:

Kamal Jain,

Vijay V. VaziraniAuthors Info & Claims

APPROX '00: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization

Pages 177 - 183

Published: 05 September 2000 Publication History

Abstract

We consider a fault tolerant version of the metric facility location problem in which every city, j, is required to be connected to r_j facilities. We give the first non-trivial approximation algorithm for this problem, having an approximation guarantee of 3 ċ H_k, where k is the maximum requirement and H_k is the k-th harmonic number. Our algorithm is along the lines of [2] for the generalized Steiner network problem. It runs in phases, and each phase, using a generalization of the primal-dual algorithm of [4] for the metric facility location problem, reduces the maximum residual requirement by 1.

References

[1]

A. Agrawal, P. Klein, and R. Ravi. When trees collide: An approximation algorithm the generalized Steiner problem on networks. SIAM J. on Computing, 24:440- 456, 1995.

Crossref

Google Scholar

[2]

M. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, E. Tardos, and D. Williamson. Improved approximation algorithms for network design problems. Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, 223-232, 1994.

Crossref

Google Scholar

[3]

M. X. Goemans, D. P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal of Computing, 24:296-317, 1995.

Crossref

Google Scholar

[4]

K. Jain and V.V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. To appear in JACM.

Crossref

Google Scholar

[5]

D.P. Williamson, M.X. Goemans, M. Mihail, and V.V. Vazirani. A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica, 15:435-454, December 1995.

Google Scholar

Cited By

View all

(2015)Improved approximation algorithms for constrained fault-tolerant resource allocationTheoretical Computer Science10.1016/j.tcs.2015.02.029590:C(118-128)Online publication date: 26-Jul-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.02.029
Liao KShen HGuo L(2013)Improved approximation algorithms for constrained fault-tolerant resource allocationProceedings of the 19th international conference on Fundamentals of Computation Theory10.1007/978-3-642-40164-0_23(236-247)Online publication date: 19-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40164-0_23
Liao KShen H(2012)Approximating the reliable resource allocation problem using inverse dual fittingProceedings of the Eighteenth Computing: The Australasian Theory Symposium - Volume 12810.5555/2523693.2523703(75-82)Online publication date: 31-Jan-2012
https://dl.acm.org/doi/10.5555/2523693.2523703
Show More Cited By

Index Terms

An approximation algorithm for the fault tolerant metric facility location problem
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Index terms have been assigned to the content through auto-classification.

Recommendations

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location (UFL) problem, which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye, and Zhang. Note that the approximability lower bound by Guha ...
An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem
Abstract
We consider a fault tolerant version of the metric facility location problem in which every city, j, is required to be connected to r_j facilities. We give the first non-trivial approximation algorithm for this problem, having an approximation ...
Fault-tolerant facility location: a randomized dependent LP-Rounding algorithm
IPCO'10: Proceedings of the 14th international conference on Integer Programming and Combinatorial Optimization

We give a new randomized LP-rounding 1.725-approximation algorithm for the metric Fault-Tolerant Uncapacitated Facility Location problem. This improves on the previously best known 2.076-approximation algorithm of Swamy & Shmoys. To the best of our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

APPROX '00: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization

September 2000

272 pages

ISBN:3540679960

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 05 September 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

(2015)Improved approximation algorithms for constrained fault-tolerant resource allocationTheoretical Computer Science10.1016/j.tcs.2015.02.029590:C(118-128)Online publication date: 26-Jul-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.02.029
Liao KShen HGuo L(2013)Improved approximation algorithms for constrained fault-tolerant resource allocationProceedings of the 19th international conference on Fundamentals of Computation Theory10.1007/978-3-642-40164-0_23(236-247)Online publication date: 19-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40164-0_23
Liao KShen H(2012)Approximating the reliable resource allocation problem using inverse dual fittingProceedings of the Eighteenth Computing: The Australasian Theory Symposium - Volume 12810.5555/2523693.2523703(75-82)Online publication date: 31-Jan-2012
https://dl.acm.org/doi/10.5555/2523693.2523703
Liao KShen H(2011)Unconstrained and constrained fault-tolerant resource allocationProceedings of the 17th annual international conference on Computing and combinatorics10.5555/2033094.2033142(555-566)Online publication date: 14-Aug-2011
https://dl.acm.org/doi/10.5555/2033094.2033142
Xu SShen H(2009)The Fault-Tolerant Facility Allocation ProblemProceedings of the 20th International Symposium on Algorithms and Computation10.1007/978-3-642-10631-6_70(689-698)Online publication date: 5-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10631-6_70
Swamy CShmoys D(2008)Fault-tolerant facility locationACM Transactions on Algorithms10.1145/1383369.13833824:4(1-27)Online publication date: 22-Aug-2008
https://dl.acm.org/doi/10.1145/1383369.1383382
Jain KMahdian MMarkakis ESaberi AVazirani V(2003)Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPJournal of the ACM10.1145/950620.95062150:6(795-824)Online publication date: 1-Nov-2003
https://dl.acm.org/doi/10.1145/950620.950621
Andreev KMaggs BMeyerson ASitaraman RRosenberg AMeyer auf der Heide F(2003)Designing overlay multicast networks for streamingProceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures10.1145/777412.777437(149-158)Online publication date: 7-Jun-2003
https://dl.acm.org/doi/10.1145/777412.777437
Guha SMeyerson AMunagala K(2003)A constant factor approximation algorithm for the fault-tolerant facility location problemJournal of Algorithms10.1016/S0196-6774(03)00056-748:2(429-440)Online publication date: 1-Sep-2003
https://dl.acm.org/doi/10.1016/S0196-6774%2803%2900056-7
Guha SMeyerson AMunagala KKosaraju S(2001)Improved algorithms for fault tolerant facility locationProceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms10.5555/365411.365554(636-641)Online publication date: 9-Jan-2001
https://dl.acm.org/doi/10.5555/365411.365554
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem