Vertex sparsifiers: New results from old techniques

Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

21 Zitate (Scopus)

Abstract

Given a capacitated graph G = (V,E) and a set of terminals K ⊆ V, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between the terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow-sparsifier for G.) What if we want H to be a "simple" graph? What if we allow H to be a convex combination of simple graphs? Improving on results of Moitra [FOCS 2009] and Leighton and Moitra [STOC 2010], we give efficient algorithms for constructing: (a) a flow-sparsifier H that maintains congestion up to a factor of O(log k)/log log k), where k = |K|. (b) a convex combination of trees over the terminals K that maintains congestion up to a factor of O(logk). (c) for a planar graph G, a convex combination of planar graphs that maintains congestion up to a constant factor. This requires us to give a new algorithm for the 0-extension problem, the first one in which the preimages of each terminal are connected in G. Moreover, this result extends to minor-closed families of graphs. Our bounds immediately imply improved approximation guarantees for several terminal-based cut and ordering problems.

OriginalspracheEnglisch
TitelApproximation, Randomization, and Combinatorial Optimization
UntertitelAlgorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings
Seiten152-165
Seitenumfang14
DOIs
PublikationsstatusVeröffentlicht - 2010
Extern publiziertJa
Veranstaltung13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 - Barcelona, Spanien
Dauer: 1 Sept. 20103 Sept. 2010

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band6302 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Konferenz

Konferenz13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
Land/GebietSpanien
OrtBarcelona
Zeitraum1/09/103/09/10

Fingerprint

Untersuchen Sie die Forschungsthemen von „Vertex sparsifiers: New results from old techniques“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren