Englert, Matthias, Gupta, Anupam, Krauthgamer, Robert, Raecke, Harald, Talgam-Cohen, 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, 01-03 Sep 2010. Published in: Lecture Notes in Computer Science, Vol.6302 pp. 152-165.

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 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 = 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 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)
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
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer
ISBN:	978-3-642-15368-6
ISSN:	0302-9743
Editor:	Serna, M and Shaltiel, R and Jansen, K and Rolim, J
Date:	2010
Volume:	Vol.6302
Number of Pages:	14
Page Range:	pp. 152-165
Identification Number:	10.1007/978-3-642-15369-3_12
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access
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:	01-03 Sep 2010
URI:	http://wrap.warwick.ac.uk/id/eprint/4700

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item