Optimal hierarchical decompositions for congestion minimization in networks

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

235 Zitate (Scopus)

Abstract

Hierarchical graph decompositions play an 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 on 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 on 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 an O(log2 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, wdiich 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 an 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(log1-5 n) approximation by Feige and Krauthgamer [17].

OriginalspracheEnglisch
TitelSTOC'08
UntertitelProceedings of the 2008 ACM Symposium on Theory of Computing
Herausgeber (Verlag)Association for Computing Machinery
Seiten255-263
Seitenumfang9
ISBN (Print)9781605580470
DOIs
PublikationsstatusVeröffentlicht - 2008
Extern publiziertJa
Veranstaltung40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Kanada
Dauer: 17 Mai 200820 Mai 2008

Publikationsreihe

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Konferenz

Konferenz40th Annual ACM Symposium on Theory of Computing, STOC 2008
Land/GebietKanada
OrtVictoria, BC
Zeitraum17/05/0820/05/08

Fingerprint

Untersuchen Sie die Forschungsthemen von „Optimal hierarchical decompositions for congestion minimization in networks“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren