The Library
Vertex sparsifiers : new results from old techniques
Tools
Englert, Matthias, Gupta, Anupam, Krauthgamer, Robert, Räcke, Harald, Talgam-Cohen, Inbal and Talwar, Kunal (2010) Vertex sparsifiers : new results from old techniques. In: 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, , , Barcelona, Spain, 1-3 Sep 2010. Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Volume 6302 pp. 152-165. ISBN 9783642153686. doi:10.1007/978-3-642-15369-3_12 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-15369-3_12
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(logkloglogk), 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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | ||||
Publisher: | Springer Berlin Heidelberg | ||||
ISBN: | 9783642153686 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | ||||
Editor: | Serna , Maria and Shaltiel , Ronen and Jansen , Klaus and Rolim, José | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Volume 6302 | ||||
Page Range: | pp. 152-165 | ||||
DOI: | 10.1007/978-3-642-15369-3_12 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, , | ||||
Type of Event: | Workshop | ||||
Location of Event: | Barcelona, Spain | ||||
Date(s) of Event: | 1-3 Sep 2010 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |