2004 | OriginalPaper | Chapter
Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems
Authors : R. Ravi, Amitabh Sinha
Published in: Integer Programming and Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the design of approximation algorithms for stochastic combinatorial optimization problems. We formulate the problems in the framework of two-stage stochastic optimization, and provide nearly tight approximations. Our problems range from the simple (shortest path, vertex cover, bin packing) to complex (facility location, set cover), and contain representatives with different approximation ratios.The approximation ratio of the stochastic variant of a typical problem is of the same order of magnitude as its deterministic counterpart. Furthermore, common techniques for designing approximation algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be carefully adapted to obtain these results.