The Library
Optimal hierarchical decompositions for congestion minimization in networks
Tools
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. ISBN 978-1-60558-047-0. ISSN 0737-8017.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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].
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Computer networks, Routing (Computer network management), Trees (Graph theory) | ||||
Journal or Publication Title: | Annual Proceedings of the 40th ACM Symposium on the Theory of Computing | ||||
Publisher: | Association for Computing Machinery, Inc. | ||||
ISBN: | 978-1-60558-047-0 | ||||
ISSN: | 0737-8017 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Number of Pages: | 9 | ||||
Page Range: | pp. 255-263 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |