Chapter 8

Provably Near-Optimal Approximation Algorithms for Operations Management Models

Retsef Levi
Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, retsef@mit.edu

Abstract
Multistage stochastic optimization models arise in various application domains, including central areas of operations management, such as inventory control, supply chain management, and revenue management. Unfortunately, it is usually computationally very hard to find optimal solutions for these fundamental models, and typically even finding good solutions is very challenging, both in theory and practice. In this tutorial, we will survey various relatively new algorithmic and performance analysis techniques that can be applied to some of these models to construct provably near-optimal algorithms, particularly algorithms that admit worst-case performance guarantees. These techniques span ideas from various disciplines, such as optimization, computer science, and stochastic analysis.

Key words: approximation algorithms; inventory control; revenue management; stochastic control

Download Chapter 8 - Password-protected content.

The 2010 volume of the TutORials in Operations Research series will be available to people who have registered for the 2010 INFORMS Annual Meeting. All INFORMS members will be able to access TutORials after January 1, 2011. Printed TutORials books from this and previous years can also be ordered here, along with CDs from 2005 to 2009.

For login instructions click here.

________________________________________________

Citation Information:

Levi, R. 2010. Provably near-optimal approximation algorithms for operations management models. J. J. Hasenbein, ed. INFORMS TutORials in Operations Research, Vol. 7. INFORMS, Hanover, MD, pp. 179–192.