The Library
Vertex sparsifiers : new results from old techniques
Tools
Tools
Tools
Englert, Matthias, Gupta, A., Krauthgamer, Robert, Räcke, Harald, Talgam-Cohen, Inbal and Talwar, Kunal (2010) Vertex sparsifiers : new results from old techniques. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science (6302). Springer Verlag, pp. 152-165. ISBN 9783642153686
Full text not available from this repository.
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 ${\smash{O(\frac{\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.
| Item Type: | Book Item |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science > Computer Science |
| Series Name: | Lecture Notes in Computer Science |
| Publisher: | Springer Verlag |
| ISBN: | 9783642153686 |
| Book Title: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |
| Date: | 2010 |
| Number: | 6302 |
| Page Range: | pp. 152-165 |
| Identification Number: | 10.1007/978-3-642-15369-3_12 |
| Status: | Not Peer Reviewed |
| Publication Status: | Published |
| Related URLs: | |
| URI: | http://wrap.warwick.ac.uk/id/eprint/47422 |
Actions (login required)
 |
View Item |
