Can I read Boosted Sampling: Approximation Algorithms for Stochastic Optimization on EtoBox?

Boosted Sampling: Approximation Algorithms for Stochastic Optimization by Anupam Gupta; Martin Pál; R. Ravi; Amitabh Sinha is a scholarly article available to read on EtoBox.

What is Boosted Sampling: Approximation Algorithms for Stochastic Optimization about?

Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the STEINER TREE problem, for example, edges must be chosen to connect terminals (clients); in VERTEX COVER, vertices must be chosen to cover edges (clients); in FACILITY LOCATION, facilities must be chosen and demand vertices (clients) connected to these chosen facilities. We consider a stochastic version of such a problem where the solution is constructed in two stages: Before the actual requirements materialize, we can choose elements in a first stage. The actual requirements are then revealed, drawn from a pre-specified probability distribution π; thereupon, some more elements may be chosen to obtain a feasible solution for the actual requirements. However, in this second (recourse) stage, choosing an element is costlier by a factor of σ > 1. The goal is to minimize the first stage cost plus the expected second stage cost. We give a general yet simple technique to adapt approximation algorithms for several deterministic problems to their stochastic versions via the following method.

Author

Anupam Gupta; Martin Pál; R. Ravi; Amitabh Sinha

Publisher

ACM

Published

2004

Language

EN