University of Warwick
4pm Tuesday 6th May 2008
Room 2511, JCMB, King's Buildings
An oblivious routing protocol makes its routing decisions independent of the traffic in the underlying network. This means that the path chosen for a routing request may only depend on its source node, its destination node, and on some random input. In spite of these serious limitations it has been shown that there are oblivious routing algorithms that obtain a polylogarithmic competitive ratios w.r.t. the congestion in the network (i.e., maximum load of a network link).
We present a new hierarchical decomposition technique that leads to good oblivious routing algorithms. This decomposition can also be used as a generic tool for solving a large variety of cut based problems in undirected graphs. As one example a straightforward dynamic programming algorithm based on the decomposition gives an O(log n)-approximation to the Minimum Bisection problem improving on a result of Feige and Krauthgamer who obtained a ratio of O(\log^1.5 n).