a polynomial-time tree decomposition to minimize congestion
Rcke recently gave a remarkable proof showing that any undirected multicommodity flow problem can be routed in an oblivious fashion with congestion that is within a factor of O (log 3 n ) of the best off-line solution to the problem. He also presented interesting applications of this result to distributed computing. Maggs, Miller, Parekh, Ravi and Wu have shown that such a decomposition also has an application to speeding up iterative solvers of linear systems. Rcke's construction finds a decomposition tree of the underlying graph, along with a method to obliviously route in a hierarchical fashion on the tree. The construction, however, uses exponential-time procedures to build the decomposition. The non-constructive nature of his result was remedied, in part, by Azar, Cohen, Fiat, Kaplan, and Rcke, who gave a polynomial time method for building an oblivious routing strategy. Their construction was not based on finding a hierarchical decomposition, and this precludes its application to iterative methods for solving linear systems. In this paper, we show how to compute a hierarchical decomposition and a corresponding oblivious routing strategy in polynomial time. In addition, our decomposition gives an improved competitive ratio for congestion of O (log 2 n log log n ). In an independent result in this conference, Bienkowski, Korzeniowski, and Rcke give a polynomial-time method for constructing a decomposition tree with competitive ratio O (log 4 n ). We note that our original submission used essentially the same algorithm, and we appreciate them allowing us to present this improved version.
tree decomposition congestion oblivious routing preconditioning