Quick and good facility location

ABSTRACT

We consider the facility location problem with shortest path distances in a weighted graph. W.h.p., we get an approximation factor of 1.62 in O(n + m) time with n and m the number of nodes and edges. Also, as a kind of warm-up, for a metric with a constant-times distance oracle, we get the factor 1.62 deterministically in O(n² log n) time.Our results build on a recent facility location algorithm of Jain, Mahdian, and Saberi (STOC'02) achieving an approximation factor of 1.61 in O(n³) time.

REFERENCES

• 1: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 2: Richard Cole , Ramesh Hariharan , Moshe Lewenstein , Ely Porat, A faster implementation of the Goemans-Williamson clustering algorithm, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.17-25, January 07-09, 2001, Washington, D.C., United States
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: G. Cornuejols, G.L. Nemhauser, and L.A. Wolsley. The uncapacitated facility location problem. In P. Mirchandani and R. Francis, editors, Discrete Location Theory, pages 97--106. John-Wiley and Sons, Inc., 1986.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 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: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 8: Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301366]
• 9: 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]
• 10: S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang. On the placement of Internet intrumentations. In Proc. 19th INFOCOM, pages 26--30, 2000.
• 11: A.A. Kuehn and M.J. Hamburger. A heuristic prograom for locating warehouses. Management Science, 9:643--666, 1963.
• 12: B. Li, M. Golin, G. G. Italiano, X. Deng, and K. Sohraby. On the optimal placement of web proxies in the Internet. In Proc. 18th INFOCOM, pages 1282--1290, 1999.
• 13: 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
• 14: M. Mahdian, Y. Ye, and J. Zhang. Improved approximation algorithms for metric facility location problems, 2002.
• 15: 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
• 16: L. Qiu, V. N. Padmanabhan, and G. M. Voelker. On the optimal placement of web server replicas. In Proc. 20th INFOCOM, pages 1587--1596, 2001.
• 17: B.C. Tansel, R.L. Francis, and T.J. Lowe. Location on networks: A survey, part 1 and 2. Management Science, 29(4):482--511, 1983.
• 18: 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

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems
      G.2.3 Applications

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management

General Terms:
Algorithms, Management, Theory

Keywords:
efficient approximation algorithms, facility location, shortest paths