The Library
Vertex sparsifiers : new results from old techniques
Tools
Englert, Matthias, Gupta, A., Krauthgamer, Robert, Räcke, Harald, TalgamCohen, Inbal and Talwar, Kunal (2010) Vertex sparsifiers : new results from old techniques. In: Serna, Maria and Shaltiel, Ronen and Jansen, Klaus and Rolim, José, (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science (6302). Springer Verlag, pp. 152165. ISBN 9783642153686
Text
fulltext17.pdf  Published Version Embargoed item. Restricted access to Repository staff only Download (234Kb) 
Official URL: http://dx.doi.org/10.1007/9783642153693_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 flowsparsifier 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 flowsparsifier 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 0extension problem, the first one in which the preimages of each terminal are connected in G. Moreover, this result extends to minorclosed families of graphs.Our bounds immediately imply improved approximation guarantees for several terminalbased 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  
Library of Congress Subject Headings (LCSH):  Computer terminals, Graph algorithms  
Series Name:  Lecture Notes in Computer Science  
Publisher:  Springer Verlag  
ISBN:  9783642153686  
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: 


Number:  6302  
Page Range:  pp. 152165  
DOI:  10.1007/9783642153693_12  
Status:  Not Peer Reviewed  
Publication Status:  Published  
Description:  
Funder:  Engineering and Physical Sciences Research Council (EPSRC), University of Warwick. Centre for Discrete Mathematics and Its Applications  
Version or Related Resource:  Conference paper. http://wrap.warwick.ac.uk/id/eprint/4700  
Related URLs: 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 