Personal tools
You are here: Home Events Abstract Archives 2007-2008 Optimal Hierarchical Decompositions for Congestion Minimisation in Networks

Optimal Hierarchical Decompositions for Congestion Minimisation in Networks

Harald Räcke 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).

Document Actions