A plant location guide for the unsure

ABSTRACT

This paper studies an extension of the k-median problem where we are given a metric space (V, d) and not just one but m client sets {S_i ⊆ V}_i^m=1, and the goal is to open k facilities F to minimize: max_i∈[m] {Σ_j∈Si d(j, F)}, i.e., the worst-case cost over all the client sets. This is a "min-max" or "robust" version of the k-median problem; however, note that in contrast to previous papers on robust/stochastic problems, we have only one stage of decision-making---where should we place the facilities? We present an O(log n + log m) approximation for robust k-median: The algorithm is combinatorial and very simple, and is based on reweighting/Lagrangean-relaxation ideas. In fact, we give a general framework for (minimization) facility location problems where there is a bound on the number of open facilities. For robust and stochastic versions of such location problems, we show that if the problem satisfies a certain "projection" property, essentially the same algorithm gives a logarithmic approximation ratio in both versions. We use our framework to give the first approximation algorithms for robust/stochastic versions of k-tree, capacitated k-median, and fault-tolerant k-median.

REFERENCES

• 1: 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]
• 2: Birge, J. R., and Louveaux, F. Introduction to stochastic programming. Springer Series in Operations Research. Springer-Verlag, New York, 1997.
• 3: Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
• 4: Charikar, M., Chekuri, C., and Pál, M. Sampling bounds for stochastic optimization. In Approximation, randomization and combinatorial optimization, vol. 3624 of Lecture Notes in Comput. Sci. Springer, Berlin, 2005, pp. 257--269.
• 5: 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]
• 6: 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]
• 7: Marek Chrobak , Claire Kenyon , Neal Young, The reverse greedy algorithm for the metric k-median problem, Information Processing Letters, v.97 n.2, p.68-72, 31 January 2006 [doi>10.1016/j.ipl.2005.09.009]
• 8: Julia Chuzhoy , Yuval Rabani, Approximating k-median with non-uniform capacities, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Cooper, L. Bounds on the Weber problem solution under conditions of uncertainty. Journal of Regional Science 18, 1 (1978), 87--93.
• 10: Daskin, M., and Owen, S. Location models in transportation. Handbook of Transportation Science (1999), 311--360.
• 11: Kedar Dhamdhere , Vineet Goyal , R. Ravi , Mohit Singh, How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.367-378, October 23-25, 2005 [doi>10.1109/SFCS.2005.42]
• 12: Even, G., Garg, N., Könemann, J., Ravi, R., and Sinha, A. Min-max tree covers of graphs. Oper. Res. Lett. 32, 4 (2004), 309--315.
• 13: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 14: Feige, U., Jain, K., Mahdian, M., and Mirrokni, V. Robust combinatorial optimization with exponential scenarios. In 12th IPCO (2007), pp. 439--453.
• 15: Feige, U., Kortsarz, G., and Peleg, D. The dense k-subgraph problem. Algorithmica 29, 3 (2001), 410--421.
• 16: Rajiv Gandhi , Samir Khuller , Srinivasan Parthasarathy , Aravind Srinivasan, Dependent rounding and its applications to approximation algorithms, Journal of the ACM (JACM), v.53 n.3, p.324-360, May 2006 [doi>10.1145/1147954.1147956]
• 17: Golovin, D., Goyal, V., and Ravi, R. Pay today for a rainy day: Improved approximation algorithms for demand-robust min-cut and shortest path problems. In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science, STACS 2006 (2006), B. Durand and W. Thomas, Eds., vol. 3884 of Lecture Notes in Computer Science, Springer-Verlag, pp. 206--217.
• 18: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 19: Hochbaum, D., and Shmoys, D. A best possible heuristic for the k-center problem. Math. Oper. Res. 10, 2 (1985), 180--184.
• 20: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 21: 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]
• 22: Subhash Khot, Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique, SIAM Journal on Computing, v.36 n.4, p.1025-1071, December 2006 [doi>10.1137/S0097539705447037]
• 23: Krause, A., McMahan, B., Guestrin, C., and Gupta, A. Selecting observations under multiple objectives. submitted, 2007.
• 24: Guolong Lin , Chandrashekhar Nagarajan , Rajmohan Rajaraman , David P. Williamson, A general approach for incremental approximation and hierarchical clustering, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1147-1156, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109684]
• 25: Louveaux, F. Stochastic location analysis. Location Science 1 (1993), 127--154.
• 26: 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
• 27: Mirchandani, P., and Odoni, A. Locations of Medians on Stochastic Networks. Transportation Science 13 (1979), 85--97.
• 28: Ravi, R., and Sinha, A. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In 10th IPCO (2004), pp. 101--115.
• 29: Rosenblatt, M. J., and Lee, H. L. A robustness approach to facilities design. International Journal of Production Research 25 (1987), 479--486.
• 30: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 31: Sheppard, E. A conceptual framework for dynamic location allocation analysis. Environment and Planning A 6(5) (1974), 547--564.
• 32: David B. Shmoys , Chaitanya Swamy, An approximation scheme for stochastic linear programming and its application to stochastic integer programs, Journal of the ACM (JACM), v.53 n.6, p.978-1012, November 2006 [doi>10.1145/1217856.1217860]
• 33: Snyder, L. Facility location under uncertainty: a review. IIE Transactions 38, 7 (2006), 547--564.
• 34: 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
• 35: van Hentenryck, P., Bent, R., and Upfal, E. Online stochastic optimization under time constraints. Annals of Operations Research (2007). To appear.
• 36: Weaver, J., and Church, R. Computational procedure for location problems on stochastic networks. Transportation Science 17, 2 (1983), 168--180.
• 37: Welzl, E. Suchen und Konstruieren durch Verdoppeln. In Highlights der Informatik, I. Wegener, Ed. Springer, Berlin, Germany, 1996, pp. 221--228.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems

  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, Design, Theory