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.

Abstract

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 [16]. 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 [17].

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item