Boosted sampling: approximation algorithms for stochastic optimization.
Anupam GuptaMartin PálR. RaviAmitabh SinhaPublished in: STOC (2004)
Keyphrases
- approximation algorithms
- stochastic optimization
- np hard
- multistage
- worst case
- minimum cost
- special case
- primal dual
- vertex cover
- set cover
- open shop
- constant factor
- approximation schemes
- precedence constraints
- approximation guarantees
- sample size
- undirected graph
- approximation ratio
- constant factor approximation
- polynomial time approximation
- randomized algorithms
- benchmark problems
- computational complexity
- scheduling problem
- disjoint paths
- greedy algorithm