A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems

References

• Arya V., Garg N., Khandekar R., Meyerson A., Munagala K., Pandit V. Local search heuristics for k-median and facility location problems. SIAM J. Comput. (2004) 33(3):544–562Crossref, Google Scholar
• Birge J. R., Louveaux F.Introduction to Stochastic Programming (1997) (Springer-Verlag, New York) Springer Series in Operations ResearchGoogle Scholar
• Blum A., Fiat A., Woeginger G. On-line algorithms in machine learning. Online Algorithms: The State of the Art (1998) (Springer-Verlag, London) 306–325Crossref, Google Scholar
• Cesa-Bianchi N., Lugosi G.Prediction, Learning, and Games (2006) (Cambridge University Press, New York) Crossref, Google Scholar
• Charikar M., Chekuri C., Pál M. Sampling bounds for stochastic optimization. Approximation, Randomization and Combinatorial Optimization (2005) 3624(Springer, Berlin) 257–269Lecture Notes in Computer ScienceCrossref, Google Scholar
• Charikar M., Guha S. Improved combinatorial algorithms for facility location problems. SIAM J. Comput. (2005) 34(4):803–824Crossref, Google Scholar
• Charikar M., Guha S., Tardos É., Shmoys D. B. A constant-factor approximation algorithm for the k-median problem. J. Comput. System Sci. (2002) 65(1):129–149Crossref, Google Scholar
• Chrobak M., Kenyon C., Young N. The reverse greedy algorithm for the metric k-median problem. Inform. Process. Lett. (2006) 97(2):68–72Crossref, Google Scholar
• Chuzhoy J., Rabani Y. Approximating k-median with non-uniform capacities. Proc. Sixteenth Annual ACM-SIAM Sympos. Discrete Algorithms (2005) (ACM, New York) 952–958Google Scholar
• Cook W. J., Cunningham W. H., Pulleyblank W. R., Schrijver A.Combinatorial Optimization (1998) (John Wiley and Sons, New York) Google Scholar
• Cooper L. Bounds on the Weber problem solution under conditions of uncertainty. J. Regional Sci. (1978) 18(1):87–93Crossref, Google Scholar
• Daskin M. S., Owen S. H. Location models in transportation. Handbook of Transportation Science (1999) (Kluwer Academic, Norwell, MA) 311–360Crossref, Google Scholar
• Dhamdhere K., Goyal V., Ravi R., Singh M. How to pay, come what may: Approximation algorithms for demand-robust covering problems. Proc. 46th Sympos. Foundations Comput. Sci. (FOCS) (2005) (IEEE Computer Society, Washington, DC) 367–378Google Scholar
• Feige U. Relations between average case complexity and approximation complexity. Proc. Thirty-Fourth Annual ACM Sympos. Theory Comput. (2002) (ACM, New York) 534–543Google Scholar
• Feige U., Jain K., Mahdian M., Mirrokni V. Robust combinatorial optimization with exponential scenarios. Proc. 12th Internat. Conf. Integer Programming Combin. Optim. (2007) (Springer-Verlag, Berlin) 439–453Google Scholar
• Feige U., Kortsarz G., Peleg D. The dense k-subgraph problem. Algorithmica (2001) 29(3):410–421Crossref, Google Scholar
• Gandhi R., Khuller S., Parthasarathy S., Srinivasan A. Dependent rounding and its applications to approximation algorithms. J. ACM (2006) 53(3):324–360Crossref, Google Scholar
• Golovin D., Goyal V., Ravi R. Pay today for a rainy day: Improved approximation algorithms for demand-robust min-cut and shortest path problems. Proc. 23rd Sympos. Theoret. Aspects Comput. Sci. (2006) (Springer-Verlag, Berlin) 206–217Google Scholar
• Gupta A., Pal M., Ravi R., Sinha A. Boosted sampling: Approximation algorithms for stochastic optimization. Proc. 36th Annual ACM Sympos. Theory Comput. (2004) (ACM, New York) 417–426Crossref, Google Scholar
• Hochbaum D., Shmoys D. B. A best possible heuristic for the k-center problem. Math. Oper. Res. (1985) 10(2):180–184Link, Google Scholar
• Hoffman A. J. Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. Sympos. Appl. Math. (1960) 10:113–127Crossref, Google Scholar
• Immorlica N., Karger D., Minkoff M., Mirrokni V. S. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. Proc. Fifteenth Annual ACM-SIAM Sympos. Discrete Algorithms (2004) (SIAM, Philadelphia) 691–700Google Scholar
• Jain K., Vazirani V. V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM (2001) 48(2):274–296Crossref, Google Scholar
• Khot S. Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. (2006) 36(4):1025–1071Crossref, Google Scholar
• Krause A., McMahan B., Guestrin C., Gupta A. Selecting observations under multiple objectives. Adv. Neural Inform. Processing Systems (2007) 20Google Scholar
• Lin G., Nagarajan C., Rajaraman R., Williamson D. P. A general approach for incremental approximation and hierarchical clustering. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithms (2006) (ACM, New York) 1147–1156Google Scholar
• Louveaux F. Stochastic location analysis. Location Sci. (1993) 1:127–154Google Scholar
• Mettu R. R., Plaxton C. G. The online median problem. SIAM J. Comput. (2003) 32(3):816–832Crossref, Google Scholar
• Mirchandani P. B., Odoni A. R. Locations of medians on stochastic networks. Transportation Sci. (1979) 13:85–97Link, Google Scholar
• Motwani R., Raghavan P.Randomized Algorithms (1995) (Cambridge University Press, New York) Crossref, Google Scholar
• Plotkin S. A., Shmoys D. B., Tardos E. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. (1995) 20(2):257–301Link, Google Scholar
• Ravi R., Sinha A. Hedging uncertainty: Approximation algorithms for stochastic optimization problems. Math. Programming (2006) 108(1):97–114Crossref, Google Scholar
• Rosenblatt M. J., Lee H. L. A robustness approach to facilities design. Internat. J. Production Res. (1987) 25:479–486Crossref, Google Scholar
• Sahni S., Gonzalez T. P-complete approximation problems. J. ACM (1976) 23:555–565Crossref, Google Scholar
• Sheppard E. S. A conceptual framework for dynamic location allocation analysis. Environment Planning A (1974) 6(5):547–564Crossref, Google Scholar
• Shmoys D. B., Swamy C. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM (2006) 53(6):978–1012Crossref, Google Scholar
• Snyder L. V. Facility location under uncertainty: A review. IIE Trans. (2006) 38(7):547–564Crossref, Google Scholar
• Swamy C., Shmoys D. B. Fault-tolerant facility location. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (2003) (Society for Industrial and Applied Mathematics, Philadelphia) 735–736Google Scholar
• Van Hentenryck P., Bent R., Upfal E. Online stochastic optimization under time constraints. Ann. Oper. Res.:1–33 http://springerlink.com/content/e53ux62618717244/Google Scholar
• Vazirani V. V.Approximation Algorithms (2001) (Springer-Verlag, Berlin) Google Scholar
• Weaver J. R., Church R. L. Computational procedure for location problems on stochastic networks. Transportation Sci. (1983) 17(2):168–180Link, Google Scholar
• Welzl E., Wegener I. Suchen und konstruieren durch verdoppeln. Highlights der Informatik (1996) (Springer, Berlin) 221–228Crossref, Google Scholar