TY - GEN

T1 - Towards (1 + ε)-Approximate flow sparsifiers

AU - Andoni, Alexandr

AU - Gupta, Anupam

AU - Krauthgamer, Robert

PY - 2014

Y1 - 2014

N2 - A useful approach to "compress" a large network G is to represent it with a flow-sparsifier, i.e., a small network H that supports the same flows as G, up to a factor q ≥ 1 called the quality of sparsifier. Specifically, we assume the network G contains a set of k terminals T, shared with the network H, i.e., T ⊆V(G) ∩V(H), and we want H to preserve all multicommodity flows that can be routed between the terminals T. The challenge is to construct H that is small. These questions have received a lot of attention in recent years, leading to some known tradeoffs between the sparsifier's quality q and its size \V(H)\. Nevertheless, it remains an outstanding question whether every G admits a flow-sparsifier H with quality q = 1 + ε, or even q = O(1), and size |V(H)| < f(k, ε) (in particular, independent of |V(G)| and the edge capacities). Making a first step in this direction, we present new constructions for several scenarios: Our main result is that for quasi-bipartite networks G, one can construct a (1 + ε)-flow-sparsifier of size poly(k/ ε). In contrast, exact (q = 1) sparsifiers for this family of networks are known to require size 2Ω(k) For networks G of bounded treewidth w, we construct a flow-sparsifier with quality q = O(logw/loglogw) and size O(w .poly(k)). For general networks G, we construct a sketch sk(G), that stores all the feasible multicommodity flows up to factor q = 1 + ε, and its size (storage requirement) is f(k, ε).

AB - A useful approach to "compress" a large network G is to represent it with a flow-sparsifier, i.e., a small network H that supports the same flows as G, up to a factor q ≥ 1 called the quality of sparsifier. Specifically, we assume the network G contains a set of k terminals T, shared with the network H, i.e., T ⊆V(G) ∩V(H), and we want H to preserve all multicommodity flows that can be routed between the terminals T. The challenge is to construct H that is small. These questions have received a lot of attention in recent years, leading to some known tradeoffs between the sparsifier's quality q and its size \V(H)\. Nevertheless, it remains an outstanding question whether every G admits a flow-sparsifier H with quality q = 1 + ε, or even q = O(1), and size |V(H)| < f(k, ε) (in particular, independent of |V(G)| and the edge capacities). Making a first step in this direction, we present new constructions for several scenarios: Our main result is that for quasi-bipartite networks G, one can construct a (1 + ε)-flow-sparsifier of size poly(k/ ε). In contrast, exact (q = 1) sparsifiers for this family of networks are known to require size 2Ω(k) For networks G of bounded treewidth w, we construct a flow-sparsifier with quality q = O(logw/loglogw) and size O(w .poly(k)). For general networks G, we construct a sketch sk(G), that stores all the feasible multicommodity flows up to factor q = 1 + ε, and its size (storage requirement) is f(k, ε).

UR - http://www.scopus.com/inward/record.url?scp=84902094546&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902094546&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84902094546

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 279

EP - 293

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -