A polynomial-time tree decomposition to minimize congestion

ABSTRACT

Räcke 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. Räcke'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 Räcke, 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² n log log n). In an independent result in this conference, Bienkowski, Korzeniowski, and Räcke give a polynomial-time method for constructing a decomposition tree with competitive ratio O(log⁴ n). We note that our original submission used essentially the same algorithm, and we appreciate them allowing us to present this improved version.

REFERENCES

• 1: B. Aiello , F. T. Leighton , B. Maggs , M. Newman, Fast algorithms for bit-serial routing on a hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.55-64, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97459]
• 2: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 3: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 4: B. Awerbuch and Y. Azar. Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 240--249, 1994.
• 5: Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
• 6: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 7: M. Bern, J. R. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo. Support graph preconditioners. Unpublished manuscript. Available at ftp://ftp.cs.sandia.gov/pub/papers/bahendr/support-graph.ps.gz.
• 8: Marcin Bienkowski , Miroslaw Korzeniowski , Harald Räcke, A practical algorithm for constructing oblivious routing schemes, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777418]
• 9: E. Boman and B. Hendrickson. Support theory for preconditioning. Unpublished manuscript. Available at ftp://ftp.cs.sandia.gov/pub/papers/bahendr/support-theory.ps.gz.
• 10: A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
• 11: Allan Borodin , Prabhakar Raghavan , Baruch Schieber , Eli Upfal, How much can hardware help routing?, Journal of the ACM (JACM), v.44 n.5, p.726-741, Sept. 1997 [doi>10.1145/265910.265922]
• 12: J. Fakcharoenphol and K. Talwar. Improved decompositions for graphs with excluded minors. Unpublished manuscript.
• 13: R. I. Greenberg and C. E. Leiserson. Randomized routing on fat-trees. In Proceedings of the 26th Annual Symposium on the Foundations of Computer Science, pages 241--249, 1985.
• 14: K. Gremban. Combinatorial Peconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University, Oct. 1996.
• 15: Keith D. Gremban , Gary L. Miller , Marco Zagha, Performance Evaluation of a New Parallel Preconditioner, Carnegie Mellon University, Pittsburgh, PA, 1994
• 16: C. Kaklamanis , D. Krizanc , T. Tsantilas, Tight bounds for oblivious routing in the hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.31-36, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97453]
• 17: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 18: T. Leighton and S. Rao. An approximate max-flow mincut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pages 422--431, 1988.
• 19: Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
• 20: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. In IEEE Symposium on Foundations of Computer Science, pages 577--591, 1994.
• 21: B. M. Maggs, G. L.Miller, O. Parekh, R. Ravi, and S. L. M. Wu. Solving symmetric diagonally-dominant systems by preconditioning. Unpublished manuscript, 2002.
• 22: B. Maggs , F. Meyer auf der Heide , B. Voecking , M. Westermann, Exploiting Locality for Data Management in Systems of Limited Bandwidth, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.284, October 19-22, 1997
• 23: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 24: P. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript, 1991.
• 25: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
• 26: B. Vöcking. Static and Dynamic Data Management in Networks. PhD thesis, Universität Paderborn, 1998.
• 27: Berthold Vöcking, Almost optimal permutation routing on hypercubes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.530-539, July 2001, Hersonissos, Greece [doi>10.1145/380752.380848]
• 28: T. Yeh and C. Lei. Competitive analysis of minimal oblivious routing algorithms on hypercubes. IEICE Transactions on Information and Systems, E84-D(1):65--75, Jan. 2001.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory

Keywords:
congestion, oblivious routing, preconditioning, tree decomposition