AG 1, AG 2, AG 3, AG 4, AG 5   Info

AG Audience

English

30 Minutes

Saarbrücken

In this talk we will present a paper by Gupta, Pal, Ravi and Sinha from STOC'04 which examines the power of sampling as a means for solving stochastic optimization problems and provides a general technique for designing algorithms for such problems using sampling. The paper studies several combinatorial optimization problems (Steiner tree, facility location, vertex cover) in the framework of two-stage stochastic optimization with recourse. In this model, a partial solution has to be constructed in the first stage, while the full requirements are only revealed afterwards, in the second stage. Subsequently, the solution may be completed to be feasible for the revealed demand, but purchasing elements in the second stage is costlier by a factor of sigma > 1. The objective is to minimize the sum of the first stage cost and the expected second stage cost.

Maria Minkoff

--email hidden

passcode not visible

logged in users only

Stochastic combinatorial optimization; Approximation algorithms