On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem

ABSTRACT

In combinatorial optimization, a popular approach toNP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Unfortunately, the known factor is often known to be large in pathological instances. Conventional wisdom holds that, in practice, approximation algorithms will produce solutions closer to optimal than their proven guarantees. In this paper, we use the rigorous-analysis-of-heuristics framework to investigate this conventional wisdom.We analyze the performance of 3 related approximation algorithms for the uncapacitated facility location problem (from [Jain, Mahdian, Markakis, Saberi, Vazirani, 2003] and [Mahdian, Ye, Zhang, 2002]) when each is applied to an instances created by placing n points uniformly at random in the unit square. We find that, with high probability, these 3 algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.

REFERENCES

• 1: Sang Ahn , Colin Cooper , Gerard Cornuejols , Alan Frieze, Probabilistic analysis of a relaxation for the k-median problem, Mathematics of Operations Research, v.13 n.1, p.1-31, February 1988 [doi>10.1287/moor.13.1.1]
• 2: F. Barahona and F. A. Chudak, Solving large scale uncapacitated facility location problems, in Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Kluwer Academic Publishers, (1999).
• 3: 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
• 4: 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]
• 5: G. Cornuéjols, G. L. Nemhauser and L. A. Wolsey, The Uncapacitated Facility Location Problem, Discrete Location Theory, (1990).
• 6: M. Hoefer. Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location. Proc. 2nd Intl. Workshop on Experimental and Efficient Algorithms (WEA 2003), LNCS 2647, (2003) 165--178.
• 7: 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]
• 8: 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
• 9: J. Krarup and P. M. Pruzan, The simple plant location problem: Survey and synthesis,European Journal of Operational Research 12 (1983) 36--81.
• 10: 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
• 11: 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
• 12: M. Penrose, Random Geometric Graphs, Oxford University Press, (2003).
• 13: 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]
• 14: J. M. Steele, Probability Theory and Combinatorial Optimization CBMS-NSF Regional Conference Series in Applied Mathematics -- Volume 69, SIAM, (1997).
• 15: 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
• 16: J. E. Yukich, Probability Theory of Classical Euclidean Optimization Problems, Springer-Verlag, (1998).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures; Complexity measures

General Terms:
Algorithms

Keywords:
approximation algorithms, probabilistic analysis of algorithms, uncapacitated facilty location problem