CS 789 THEORY SEMINAR [home]

Speaker:      Ara Hayrapetyan
Affiliation:    Cornell University
Date:            November 22, 2004         
Title:        Network Design for Information Networks     

Abstract: 

In this talk we will define a new class of network design problems motivated by designing information networks. In our model, the cost of transporting flow for a set of users (or servicing them by a facility) depends on the amount of information requested by the set of users. We assume that the aggregation cost follows economies of scale, that is, the incremental cost of a new user is less if the set of users already served is larger. Naturally, information requested by some sets of users might aggregate better than that of others, so our cost is now a function of the actual set of users, not just their total demand.

We provide constant-factor approximation algorithms to two important problems in this general model. In the Group Facility Location problem, each user needs information about a resource, and the cost is a linear function of the number of resources involved (instead of the number of clients served). The Dependent Maybecast Problem extends the Karger-Minkoff maybecast model to probabilities with limited correlation and also contains the 2-stage stochastic optimization problem as a special case. We also give an O(ln n)-approximation algorithm for the Single Sink Information Network Design problem.

We show that the Stochastic Steiner Tree problem can be approximated by dependent maybecast, and using this we obtain an O(1)-approximation algorithm for the k-stage stochastic Steiner tree problem for any fixed k.
Our algorithm allows scenarios to have different inflation factors, and works for any distribution provided that we can sample the distribution.

This is joint work with Chaitanya Swamy and Eva Tardos and will appear in SODA 2005.