SPEAKER: Anupam Gupta
TIME: Thursday 4:30-5:30 pm, November 2nd, 2006
PLACE: PPB 300
TITLE: Oblivious Network Design
Consider the following form of the Steiner Forest problem: for each pair of vertices {u,v} in the network, you have to decide on a *single path* P_{uv} between u and v. Now an adversary decides the set S of pairs to be connected, and you pay \$1 for each edge in the \union_{(u,v) \in S} P_{uv}.
Question: How should you choose the paths?
We show O(log^2 n)-competitive algorithm for this problem. In general, we develop a framework to model oblivious network design problems (of which the above problem is a special case), and give algorithms with poly-logarithmic competitive ratio for problems in this framework (and hence for this problem).
This is joint work with MohammadTaghi Hajiaghayi and Harald Raecke.
