Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP

ABSTRACT

In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O(m log m) and O(n³), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.

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: Balinski, M. L. 1966. On finding integer solutions to linear programs. In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems. 225--248.
• 4: Beasley, J. E. 2002. Operations research library. http://mscmga.ms.ic.ac.uk/info.html.
• 5: Craig W. Cameron , Steven H. Low , David X. Wei, High-density model for server allocation and placement, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 6: 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
• 7: 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]
• 8: 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
• 9: 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
• 10: Chudak, F. A., and Shmoys, D. 1998. Improved approximation algorithms for the uncapacitated facility location problem. Unpublished manuscript.
• 11: Chvatal, V. 1979. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 233--235.
• 12: Cornuejols, G., Nemhauser, G. L., and Wolsey, L. A. 1990. The uncapacitated facility location problem. In Discrete Location Theory, P. Mirchandani and R. Francis, Eds. Wiley, New York, 119--171.
• 13: Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Proceedings of the 4th ACM conference on Electronic commerce, p.108-114, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779942]
• 14: Goemans, M., and Kleinberg, J. 1998. An improved approximation ratio for the minimum latency problem. Math. Prog. 82, 111--124.
• 15: Michel X. Goemans , Martin Skutella, Cooperative facility location games, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.76-85, January 09-11, 2000, San Francisco, California, United States
• 16: Sudipto Guha , Rajeev Motwani, Approximation algorithms for facility location problems, 2000
• 17: 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]
• 18: 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
• 19: Sudipto Guha , Adam Meyerson , Kamesh Munagala, Improved Combinatorial Algorithms for Single Sink Edge Installation Problems., Stanford University, Stanford, CA, 2000
• 20: Sudipto Guha , Adam Meyerson , Kamesh Munagala, Improved algorithms for fault tolerant facility location, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.636-641, January 07-09, 2001, Washington, D.C., United States
• 21: Hajiaghayi, M., Mahdian, M., and Mirrokni, V. 2003. The facility location problem with general cost functions. Networks 42, 1 (Aug.), 42--47.
• 22: Hochbaum, D. S. 1982. Heuristics for the fixed cost median problem. Math. Prog. 22, 2, 148--162.
• 23: 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
• 24: 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
• 25: Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
• 26: Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., and Zhang, L. 2000. On the placement of internet instrumentations. In Proceedings of IEEE INFOCOM'00. IEEE Computer Society Press, Los Alamitos, Calif. 26--30.
• 27: Kaufman, L., van Eede, M., and Hansen, P. 1977. A plant and warehouse location problem. Oper. Res. Quart. 28, 547--557.
• 28: 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
• 29: Kuehn, A. A., and Hamburger, M. J. 1963. A heuristic program for locating warehouses. Manag. Sci. 9, 643--666.
• 30: Li, B., Golin, M., Italiano, G., Deng, X., and Sohraby, K. 1999. On the optimal placement of web proxies in the internet. In Proceedings of IEEE INFOCOM'99. IEEE Computer Society Press, Los Alamitos, Calif., 1282--1290.
• 31: Lovasz, L. 1975. On the ratio of optimal integral and fractional covers. Disc. Math. 13, 383--390.
• 32: Mohammad Mahdian , Yinyu Ye , Jiawei Zhang, Improved Approximation Algorithms for Metric Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.229-242, September 17-21, 2002
• 33: McEliece, R. J., Rodemich, E. R., Rumsey Jr., H., and Welch, L. R. 1977. New upper bounds on the rate of a code via the delsarte-macwilliams inequalities. IEEE Trans. Inf. Theory 23, 157--166.
• 34: R. R. Mettu , C. G. Plaxton, The online median problem, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.339, November 12-14, 2000
• 35: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 36: Qiu, L., Padmanabhan, V. N., and Voelker, G. M. 2001. On the placement of web server replicas. In Proceedings of IEEE INFOCOM (Anchorage, Ak.). IEEE Computer Society Press, Los Alamitos, Calif., 1587--1596.
• 37: Sridhar Rajagopalan , Vijay V. Vazirani, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs, SIAM Journal on Computing, v.28 n.2, p.525-540, April 1999 [doi>10.1137/S0097539793260763]
• 38: 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]
• 39: Stollsteimer, J. F. 1961. The effect of technical change and output expansion on the optimum number, size and location of pear marketing facilities in a California pear producing region. PhD dissertation. University of California at Berkeley.
• 40: Stollsteimer, J. F. 1963. A working model for plant numbers and locations. J. Farm Econom. 45, 631--645.
• 41: 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
• 42: 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
• 43: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 44: Zegura, E. W., Calvert, K. L., and Bhattacharjee, S. 1996. How to model an internetwork. In Proceedings of IEEE INFOCOM. Vol. 2 (San Francisco, Calif.) IEEE Computer Society Press, Los Alamitos, Calif. 594--602.

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory

Keywords:
Approximation algorithms, dual-fitting method, facility location problem, primal-dual method