A new greedy approach for facility location problems

ABSTRACT

We present a simple and natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61. We use this algorithm to find better approximation algorithms for the capacitated facility location problem with soft capacities and for a common generalization of the k-median and facility location problems. We also prove a lower bound of 1+2/e on the approximability of the k-median problem. At the end, we present a discussion about the techniques we have used in the analysis of our algorithm, including a computer-aided method for proving bounds on the approximation factor.

REFERENCES

• 1: Matthew Andrews , Lisa Zhang, The Access Network Design Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.40, November 08-11, 1998
• 2: Vijay Arya , Naveen Garg , Rohit Khandekar , Kamesh Munagala , Vinayaka Pandit, Local search heuristic for k-median and facility location problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.21-29, July 2001, Hersonissos, Greece [doi>10.1145/380752.380755]
• 3: M. L. Balinski. On finding integer solutions to linear programs. In Proc. IBM Scientific Computing Symposium on Combinatorial Problems, pages 225--248, 1966.
• 4: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 5: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
• 6: Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
• 7: Fabián A. Chudak, Improved Approximation Algorithms for Uncapitated Facility Location, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.180-194, June 22-24, 1998
• 8: F.A. Chudak and D. Shmoys. Improved approximation algorithms for the uncapacitated facility location problem. unpublished manuscript, 1998.
• 9: G. Cornuejols, G.L. Nemhauser, and L.A. Wolsey. The uncapacitated facility location problem. In P. Mirchandani and R. Francis, editors, Discrete Location Theory, pages 119--171. John Wiley and Sons Inc., 1990.
• 10: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 11: M. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. (MATH)ematical Programming, 82:111--124, 1998.
• 12: Sudipto Guha , Rajeev Motwani, Approximation algorithms for facility location problems, 2000
• 13: 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]
• 14: S. Guha , A. Meyerson , K. Munagala, Hierarchical placement and network design problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.603, November 12-14, 2000
• 15: Sudipto Guha , Adam Meyerson , Kamesh Munagala, Improved Combinatorial Algorithms for Single Sink Edge Installation Problems., Stanford University, Stanford, CA, 2000
• 16: D. S. Hochbaum. Heuristics for the fixed cost median problem. (MATH)ematical Programming, 22(2):148--162, 1982.
• 17: K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V.V. Vazirani. Approximation algorithms for facility location via dual fitting with factor-revealing lp. submitted to Combinatorica.
• 18: Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
• 19: S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. On the placement of internet instrumentations. In Proceedings of IEEE INFOCOM'00, pages 26--30, March 2000.
• 20: Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman, Analysis of a local search heuristic for facility location problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.1-10, January 25-27, 1998, San Francisco, California, United States
• 21: A.A. Kuehn and M.J. Hamburger. A heuristic program for locating warehouses. Management Science, 9:643--666, 1963.
• 22: B. Li, M. Golin, G. Italiano, Deng X., and K. Sohraby. On the optimal placement of web proxies in the internet. In Proceedings of IEEE INFOCOM'99, pages 1282--1290, 1999.
• 23: 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
• 24: M. Mahdian, Y. Ye, and J. Zhang. Improved approximation algorithms for metric facility location problems. Unpublished manuscript, 2002.
• 25: R.J. McEliece, E.R. Rodemich, H. Rumsey Jr., and L.R. Welch. New upper bounds on the rate of a code via the delsarte-macwilliams inequalities. IEEE Transactions on Information Theory, 23:157--166, 1977.
• 26: L. Qiu, V.N. Padmanabhan, and G. Voelker. On the placement of web server replicas. In Proceedings of IEEE INFOCOM'01, Anchorage, AK, USA, April 2001.
• 27: David B. Shmoys, Approximation algorithms for facility location problems, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.27-33, September 05-08, 2000
• 28: 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]
• 29: 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
• 30: Mikkel Thorup, Quick k-Median, k-Center, and Facility Location for Sparse Graphs, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.249-260, July 08-12, 2001
• 31: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

General Terms:
Algorithms, Experimentation, Performance, Theory