Optimal Hierarchical Decompositions for Congestion Minimization in Networks
Raecke, Harald (2008) Optimal Hierarchical Decompositions for Congestion Minimization in Networks. In: 40th Annual ACM International Symposium on Theory of Computing, Victoria, Canada, May 17-20, 2008. Published in: Annual Proceedings of the 40th ACM Symposium on the Theory of Computing pp. 255-263.Full text not available from this repository.
Hierarchical graph decompositions play ail important role in the design of approximation and online algorithms for graph problems. This is mainly due to the fact that the results concerning the approximation of metric spaces by tree metrics (e.g. [10, 11, 14, 16]) depend on hierarchical graph decompositions. In this line of work a probability distribution over tree graphs is constructed from a given input graph, in such a way that the tree distances closely resemble the distances in the original graph. This allows it, to solve many problems with a distance-based cost. function oil trees, and then transfer the tree solution to general undirected graphs with only a logarithmic loss in the performance guarantee. The results about oblivious routing [30, 22] in general undirected graphs are based oil hierarchical decompositions of a different type in the sense that they are aiming to approximate the bottlenecks in the network (instead of the point-to-point distances). We call such decompositions cut-based decompositions. It has been shown that they also can be used to design approximation and online algorithms for a wide variety of different problems, but at the current state of the art the performance guarantee goes down by ail O(log(2) n log log n)-factor when making the transition from tree networks to general graphs. In this paper we show how to construct cut-based decompositions that only result in a logarithmic loss in performance, which is asymptotically optimal. Remarkably, one major ingredient of our proof is a distance-based decomposition scheme due to Fakcharoenphol, Rao and Talwar . This shows an interesting relationship between these seemingly different decomposition techniques. The main applications of the new decomposition are ail optimal O(log n)-competitive algorithm for oblivious routing in general undirected graphs, and an O(log n)-approximation for Minimum Bisection, which improves the O(log 1.5 n) approximation by Feige and Krauthgamer .
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Divisions:||Faculty of Science > Computer Science|
|Journal or Publication Title:||Annual Proceedings of the 40th ACM Symposium on the Theory of Computing|
|Publisher:||Association for Computing Machinery, Inc.|
|Number of Pages:||9|
|Page Range:||pp. 255-263|
|Access rights to Published version:||Restricted or Subscription Access|
|Title of Event:||40th Annual ACM International Symposium on Theory of Computing|
|Type of Event:||Conference|
|Location of Event:||Victoria, Canada|
|Date(s) of Event:||May 17-20, 2008|
Actions (login required)