The Library
Vertex sparsifiers : new results from old techniques
Tools
Englert, Matthias, Gupta, Anupam (Researcher in Computer Science), Krauthgamer, Robert, Raecke, Harald, TalgamCohen, Inbal and Talwar, Kunal (2010) Vertex sparsifiers : new results from old techniques. In: 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010), Univ Politecnica Catalunya (UPC), Barcelona, Spain, 0103 Sep 2010
Full text not available from this repository.Abstract
Given a capacitated graph G = (V, E) and a set of terminals K subset of 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 O(log k/log log k), where k = vertical bar K vertical bar. (b) a convex combination of trees over the terminals K that maintains congestion up to a factor of O(log k). (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:  Conference Item (Paper)  

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  
Editor:  Serna, M and Shaltiel, R and Jansen, K and Rolim, J  
Official Date:  2010  
Dates: 


Identification Number:  10.1007/9783642153693_12  
Status:  Peer Reviewed  
Publication Status:  Published  
Version or Related Resource:  Englert, Matthias, Gupta, A., Krauthgamer, Robert, Räcke, Harald, TalgamCohen, 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. 152165. ISBN 9783642153686 http://wrap.warwick.ac.uk/id/eprint/47422  
Conference Paper Type:  Paper  
Title of Event:  13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010)  
Type of Event:  Workshop  
Location of Event:  Univ Politecnica Catalunya (UPC), Barcelona, Spain  
Date(s) of Event:  0103 Sep 2010  
Related URLs:  
URI:  http://wrap.warwick.ac.uk/id/eprint/4700 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 