Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar
Given a capacitated graph G = (V,E) and a set of terminals K ße 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? Such problems were studied by Moitra [FOCS 2009] and Leighton and Moitra [STOC 2010]. In this paper, we improve on their results and show the following:
These results immediately improve the approximation algorithms for several terminal-based cut and ordering problems. (We also give direct algorithms for the ordering problems with better approximation guarantees.) Apart from these positive results, we also give some lower bounds for restricted classes of flow-sparsifiers.
|Published in||APPROX 2010|