Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems |
| |
Authors: | R. Ravi Amitabh Sinha |
| |
Affiliation: | (1) Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213, USA;(2) Ross School of Business, University of Michigan, Ann Arbor, MI 48109, USA |
| |
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. |
| |
Keywords: | 20E28 20G40 20C20 |
本文献已被 SpringerLink 等数据库收录! |
|