Personal tools
You are here: Home Events Abstract Archives 2006-2007 Oblivious Network Design

Oblivious Network Design

Anupam Gupta Carnegie Mellon University 4pm Tuesday 11th July 2006 Room 2511, JCMB, King's Buildings

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.

Document Actions