Boosted sampling: Approximation algorithms for stochastic optimization

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

Research output: Contribution to journalConference articlepeer-review


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. First stage: Draw σ independent sets of clients from the distribution π and apply the approximation algorithm to construct a feasible solution for the union of these sets. Second stage: Since the actual requirements have now been revealed, augment the first-stage solution to be feasible for these requirements. We use this framework to derive constant factor approximations for stochastic versions of VERTEX COVER, STEINER TREE and UNCAPACITATED FACILITY LOCATION for arbitrary distributions π in one fell swoop. For special (product) distributions, we obtain additional and improved results. Our techniques adapt and use the notion of strict cost-shares introduced in [5].

Original languageEnglish (US)
Pages (from-to)417-426
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2004
EventProceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States
Duration: Jun 13 2004Jun 15 2004


  • Approximation algorithms
  • Boosted sampling
  • Cost sharing
  • Stochastic optimization

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Boosted sampling: Approximation algorithms for stochastic optimization'. Together they form a unique fingerprint.

Cite this