Title: Stochastic Steiner tree without the root
Speaker: Martin Pal, DIMACS
Date: March 1, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider the stochastic Steiner tree problem in the model of two-stage stochastic optimization with recourse, that recently gained traction in the theoretical computer science community. The model can be paraphrased as follows: on Monday, we only have probabilistic information about the set of terminals we will be required to connect by a Steiner tree, and we are allowed to buy some edges. On Tuesday, the set of required vertices is revealed (we assume it has been drawn from a known probability distribution), and we are required to buy enough edges to ensure that all required terminals are connected. Our goal is to design an algorithm that decides on the set of edges to buy in each stage, to minimize the expected cost of the solution.
Gupta et al. (STOC'04) recently gave a $3.55$-approximation algorithm for stochastic Steiner tree, under the assumption that the tree must always contain a specific fixed root vertex $r$. While this assumption is without loss of generality deterministic Steiner tree problem, removing it poses a nontrivial challenge in the stochastic case. In fact, an algorithm for the unrooted stochastic Steiner tree is powerful enough to solve the Multicommodity Rent-or-Buy problem (for which the best approximation known is 6.83), and its generalization we call the Group Rent-or-Buy problem, for which no approximation was previously known.
We give the first constant factor approximation algorithm for the unrooted Steiner tree problem by generalizing the cost sharing techniques developed by Gupta et al (FOCS'03) to obtain approximation algorithms for the Multicommodity Rent-or-Buy problem.
Joint work with Anupam Gupta.