CS 789 THEORY SEMINAR [home]

Speaker:    Martin Pal
Affiliation:  Cornell University
Date:          March 1, 2003
Title:          Boosted Sampling: Approximation Algorithms for Stochastic Optimization

Abstract:

Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies some requirements. For example, in the Steiner Tree problem,
edges must be chosen to connect terminals; in Vertex Cover, vertices must be chosen to cover edges.

We consider stochastic versions of optimization problems in the context of Two-Stage Stochastic Optimization with Recourse. This may be paraphrased as follows: Today, the elements are cheap, but we do not know the requirements -- we only know a distribution \pi of requirements that will be revealed tomorrow. Tomorrow, the demands are
revealed, and we need to buy additional elements, that have become more expensive by some factor \sigma, to satisfy all the revealed demands. The goal is to minimize the expected cost of elements purchased in both stages.

We give a general technique to adapt approximation algorithms for several non-stochastic problems to their stochastic versions by using a boosted random sample (by drawing \sigma times repeatedly) to construct our solution. This simple approach yields constant-factor approximation algorithms for stochastic variants of several problems including Vertex Cover, Steiner Tree, Uncapacitated Facility Location, and Single-Sink Rent-or-Buy. Our algorithms work for arbitrary
distributions \pi; furthermore, they do not require explicit knowledge of \pi, instead only requiring sampling access to the distribution. Our results substantially extend and improve previous work of Immorlica et al., and Ravi and Sinha on these stochastic problems.

This is joint work with Anupam Gupta, R. Ravi and Amitabh Sinha.