### DIMACS Theoretical Computer Science Seminar

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.