SpringerLink
Log in

Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems

  • Published:
Mathematical Programming Submit manuscript

Abstract

We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from the graph-theoretic (shortest path, vertex cover, facility location) to set-theoretic (set cover, bin packing), and contain representatives with different approximation ratios.

The approximation ratio of the stochastic variant of a typical problem is found to be of the same order of magnitude as its deterministic counterpart. Furthermore, we show that common techniques for designing approximation algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be adapted to obtain these results.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Arora, S., Sudan, M.: Improved low degree testing and applications. Combinatorica 23 (3), 365–426 (2003)

    Article  MathSciNet  Google Scholar 

  2. Ausiello, G., Crescenzi, P., Gambosi, G., Kann V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, Berlin, 1999

  3. Balinski, M.L.: On finding integer solutions to linear programs. In: Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, 1966, pp. 225–248

  4. Birge, J., Louveaux, F.: Introduction to Stochastic Programming. Springer-Verlag, Berlin, 1997

  5. Cornuéjols, G., Nemhauser, G., Wolsey, L.: The uncapacitated facility location problem. In: P. Mirchandani, R. Francis (eds.), Discrete Location Theory, Wiley, 1990, pp. 119–171

  6. Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+ ε in linear time. Combinatorica 1, 349–355 (1981)

    MATH  MathSciNet  Google Scholar 

  7. Dhamdhere, K., Ravi, R., Singh, M.: On two-stage Stochastic Minimum Spanning Trees. In: Proceedings of the 11th Integer Programming and Combinatorial Optimization Conference, 2005, pp. 321–334

  8. Dijkstra, E.: A note on two problems in connexion with graphs. Numerischke Mathematik 1, 269–271 (1959)

    Article  MATH  MathSciNet  Google Scholar 

  9. Dye, S., Stougie, L., Tomasgard, A.: Approximation algorithms and relaxations for a service provision problem on a telecommunication network. Discrete Applied Mathematics 129 (1), 63–81 (2003)

    Article  MathSciNet  Google Scholar 

  10. Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner treeproblem. J. Algorithms 37 (1), 66–84 (2000)

    Article  MathSciNet  Google Scholar 

  11. Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. J. Algorithms 31 (1), 228–248 (1999)

    Article  MathSciNet  Google Scholar 

  12. Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: A network design problem for multicommodity flow. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 389–398 (2001)

    Google Scholar 

  13. Gupta, A., Pál, M.: Stochastic Steiner trees without a root. In: Proceedings of the 32nd International Colloquium on Automata Languages and Programming, 2005, pp. 1051–1063

  14. Gupta, A., Pál, M., Ravi, R., Sinha, A.: Boosted Sampling: Approximation algorithms for stochastic optimization problems. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 417–426

  15. Gupta, A., Pál, M., Ravi, R., Sinha, A.: What about Wednesday? Approximation algorithms for multistagestochastic optimization. In: Proceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization, 2005, pp. 86–98

  16. Gupta, A., Ravi, R., Sinha, A.: An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design. In: Proceedings of the 45th Symposium on Foundations of Computer Science, 2004, pp. 218–227

  17. Halperin, E., Krauthgamer, R. Polylogarithmic inapproximability. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing 2003, pp. 585–594

  18. Klein Haneveld, W.K., van der Vlerk, M.H.: Stochastic Programming. Dept. of Econometrics and OR University of Groningen Netherlands, 2003

  19. Håstad, J.: Some optimal inapproximability results. J. ACM 48 (4), 798–859 (2001)

    Article  Google Scholar 

  20. Hayrapetyan, A., Swamy, C., Tardos, E.: Network Design for Information Networks. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 933–942

  21. Heitsch, H., Römisch, W. Scenario reduction algorithms in stochastic programming. Computational Optimization and Applications 24, 187–206 (2003)

    Google Scholar 

  22. Immorlica, N., Karger, D., Minkoff, M. Mirrokni, V.: On the Costs and Benefits of Procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 684–693

  23. Johnson, D., Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256–278 (1974)

    Google Scholar 

  24. Coffman Jr, E., Garey, M., Johnson, D.: Approximation algorithms for bin-packing: a survey. In: D.S. Hochbaum (ed.), Approximation Algorithms for NP-hard Problems, 1997, PWS

  25. Kall, P., Wallace, S.: Stochastic Programming. Wiley, 1994

  26. Karger, D., Minkoff, M.: Building Steiner trees with incomplete global knowledge. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, 2000, pp. 613–623

  27. Kleinberg, J., Rabani, Y., Tardos, E.: Allocating bandwidth for bursty connections. SIAM J Comput. 30 (1), 191–217 (2000)

    Article  MathSciNet  Google Scholar 

  28. Kong, N., Schaefer, A.: A factor 1/2 approximation algorithm for two-stage stochastic matching problems. Eur. J. Oper. Res. to appear, 2004

  29. Kumar, A., Swamy, C.: Primal-dual algorithms for connected facility location problems. Algorithmica 40 (4), 245–269 (2004)

    Article  MathSciNet  Google Scholar 

  30. Lin, J.-H., Vitter, J.: ε-approximations with minimum packing constraint violation. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 771–782

  31. Louveaux, F., Peeters, D.: A dual-based procedure for stochastic facility location. Oper. Res. 40, 564–573 (1992)

    MATH  MathSciNet  Google Scholar 

  32. Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems In: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, 2002, pp. 229–242

  33. Möhring, R., Schulz, A., Uetz, M.: Approximation in stochastic scheduling: The power of LP-based priority policies. J. ACM 46 (6), 924–942 (1999)

    Article  Google Scholar 

  34. Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex coverproblem. Acta Informatica 22, 115–123 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  35. Ravi, R., Salman, F.S.: Approximation algorithms for the traveling purchaser problem and its variants in network design. In: Proceedings of the European Symposium on Algorithms, 1999, pp. 29–40

  36. Ravi, R., Sinha, A.: Hedging uncertainty: Approximation algorithms for stochastic optimization problems. In: Proceedings of the 10th Integer Programming and Combinatorial Optimization Conference, 2004, pp. 101–115

  37. Ravi, R., Sinha, A.: Multicommodity facility location. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 342–349

  38. Schultz, R., Stougie, L., van der Vlerk, M.H.: Two-stage stochastic integer programming: a survey. Statistica Neerlandica 50 (3), 404–416 (1996)

    MathSciNet  Google Scholar 

  39. Shmoys, D., Swamy, C.: Stochastic Optimization is (almost) as Easy as Deterministic Optimization. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 228–237

  40. Shmoys, D., Swamy, C.: Sampling-based approximation algorithms for multi-stage stochastic optimization. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 357–366

  41. Shmoys, D., Swamy, C., Levi, R.: Facility location with service installation costs. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 1088–1097

  42. Shmoys, D., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems.In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 265–274

  43. Skutella, M., Uetz, M.: Stochastic machine scheduling with precedence constraints. SIAM J. Comput. 34 (4), 788–802 (2005)

    Article  MathSciNet  Google Scholar 

  44. Vazirani, V.: Approximation Algorithms. Springer-Verlag, Berlin, 2001

Download references

Author information

Authors and Affiliations

  1. Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, 15213, USA

    R. Ravi

  2. Ross School of Business, University of Michigan, Ann Arbor, MI, 48109, USA

    Amitabh Sinha

Authors
  1. R. Ravi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Amitabh Sinha
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R. Ravi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ravi, R., Sinha, A. Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems. Math. Program. 108, 97–114 (2006). https://doi.org/10.1007/s10107-005-0673-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-005-0673-5

Mathematics Subject Classification (1991)

Search

Navigation