Boosted sampling: approximation algorithms for stochastic optimization

Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. For example, in the STEINER TREE problem, 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: Be-fore 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 pi; thereupon, some more elements may be chosen to obtain a feasible solution for the actual requirements. However, in this second (re-course) 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. • First stage: Draw σ independent sets of clients from the distribution pi and apply the approximatio