Fault-tolerant facility location

ABSTRACT

We consider a fault-tolerant generalization of the classical uncapacitated facility location problem, where each client j has a requirement that r_j distinct facilities serve it, instead of just one. We give a 2.076-approximation algorithm for this problem using LP rounding, which is currently the best-known performance guarantee. Our algorithm exploits primal and dual complementary slackness conditions and is based on clustered randomized rounding. A technical difficulty that we overcome is the presence of terms with negative coefficients in the dual objective function, which makes it difficult to bound the cost in terms of dual variables. For the case where all requirements are the same, we give a primal-dual 1.52-approximation algorithm.

We also consider a fault-tolerant version of the k-median problem. In the metric k-median problem, we are given n points in a metric space. We must select k of these to be centers, and then assign each input point j to the selected center that is closest to it. In the fault-tolerant version we want j to be assigned to r_j distinct centers. The goal is to select the k centers so as to minimize the sum of assignment costs. The primal-dual algorithm for fault-tolerant facility location with uniform requirements also yields a 4-approximation algorithm for the fault-tolerant k-median problem for this case. This the first constant-factor approximation algorithm for the uniform requirements case.

REFERENCES

• 1: Ageev, A., and Sviridenko, M. 2004. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Combinatorial Optim. 8, 307--328.
• 2: Vijay Arya , Naveen Garg , Rohit Khandekar , Adam Meyerson , Kamesh Munagala , Vinayaka Pandit, Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal on Computing, v.33 n.3, p.544-562, 2004 [doi>10.1137/S0097539702416402]
• 3: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for Facility Location Problems, SIAM Journal on Computing, v.34 n.4, p.803-824, 2005 [doi>10.1137/S0097539701398594]
• 4: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem, Journal of Computer and System Sciences, v.65 n.1, p.129-149, August 2002 [doi>10.1006/jcss.2002.1882]
• 5: Fabián A. Chudak , David B. Shmoys, Improved Approximation Algorithms for the Uncapacitated Facility Location Problem, SIAM Journal on Computing, v.33 n.1, p.1-25, 2004 [doi>10.1137/S0097539703405754]
• 6: Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Journal of Algorithms, v.31 n.1, p.228-248, April 1999 [doi>10.1006/jagm.1998.0993]
• 7: Sudipto Guha , Adam Meyerson , Kamesh Munagala, A constant factor approximation algorithm for the fault-tolerant facility location problem, Journal of Algorithms, v.48 n.2, p.429-440, September 2003 [doi>10.1016/S0196-6774(03)00056-7]
• 8: Hardy, G. H., Littlewood, J. E., and Pólya, G. 1952. Inequalities. Cambridge University Press, UK.
• 9: Kamal Jain , Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM (JACM), v.50 n.6, p.795-824, November 2003 [doi>10.1145/950620.950621]
• 10: Kamal Jain , Mohammad Mahdian , Amin Saberi, A new greedy approach for facility location problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510012]
• 11: Kamal Jain , Vijay V. Vazirani, An approximation algorithm for the fault tolerant metric facility location problem, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.177-183, September 05-08, 2000
• 12: Kamal Jain , Vijay V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM (JACM), v.48 n.2, p.274-296, March 2001 [doi>10.1145/375827.375845]
• 13: Madhukar R. Korupolu , C. Greg Plaxton, Analysis of a local search heuristic for facility location problems, Journal of Algorithms, v.37 n.1, p.146-188, Oct. 2000 [doi>10.1006/jagm.2000.1100]
• 14: Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
• 15: Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani, A Greedy Facility Location Algorithm Analyzed Using Dual Fitting, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.127-137, August 18-20, 2001
• 16: Mohammad Mahdian , Yinyu Ye , Jiawei Zhang, Approximation Algorithms for Metric Facility Location Problems, SIAM Journal on Computing, v.36 n.2, p.411-432, 2006 [doi>10.1137/S0097539703435716]
• 17: Ramgopal R. Mettu , C. Greg Plaxton, The Online Median Problem, SIAM Journal on Computing, v.32 n.3, p.816-832, 2003 [doi>10.1137/S0097539701383443]
• 18: Mirchandani, P., and Francis, R. 1990. Discrete Location Theory. John Wiley, New York.
• 19: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
• 20: Maxim Sviridenko, An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.240-257, May 27-29, 2002
• 21: Chaitanya Swamy , David B. Shmoys, Fault-tolerant facility location, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 22: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
k-median problem, Approximation algorithms, facility location