LFCS Seminar

Oblivious Network Design

Anupam Gupta

Carnegie Mellon University

4pm Tuesday 11th July 2006
Room 2511, JCMB, King's Buildings

---

Abstract

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}.

How should you choose the paths?

We show O(log2 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.