Approximation Algorithms for 2-stage and Multi-stage Stochastic Optimization.
Chaitanya SwamyDavid B. ShmoysPublished in: Algorithms for Optimization with Incomplete Information (2005)
Keyphrases
- constant factor approximation
- stochastic optimization
- multistage
- approximation algorithms
- single stage
- np hard
- special case
- dynamic programming
- worst case
- minimum cost
- lot sizing
- vertex cover
- set cover
- primal dual
- precedence constraints
- constant factor
- randomized algorithms
- open shop
- approximation ratio
- optimal policy
- combinatorial auctions
- decision making
- scheduling problem
- state space
- optimal solution