Create Presentation
Download Presentation

Download Presentation
## Multi-commodity Flows and Cuts in Polymatroidal Networks

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Multi-commodity Flows and Cuts in Polymatroidal Networks**Chandra Chekuri Univ. of Illinois, Urbana-Champaign Joint work with SreeramKannan, Adnan Raja, PramodViswanath (UIUC ECE Department) Paper available at http://arxiv.org/abs/1110.6832**Max-flow Min-cut Theorem**[Ford-Fulkerson, Menger] G=(V,E) directed graph with non-negative edge-capacities max s-t flow value equal to min s-t cut value if capacities integral max flow can be chosen to be integral 1 4 10 8 t s 20 11 6**Multi-commodity Flows**1 Several pairs (s1,t1),...,(sk,tk) jointly use the network capacity to route their flow fi(e) : flow for pair i on edge e ifi(e) · c(e) for all e s3 s2 4 10 8 s1 t1 20 11 6 t3 t2**Max Throughput Flow and Min Multicut**1 fi(e) : flow for pair i on edge e ifi(e) · c(e) for all e max ival(fi)(max throughput flow) s3 s2 4 10 8 s1 t1 20 11 6 t3 t2**Max Throughput Flow and Min Multicut**1 fi(e) : flow for pair i on edge e ifi(e) · c(e) for all e max ival(fi)(max throughput flow) Multicut: set of edges whose removal disconnects all pairs Max Throughput Flow ·Min Multicut Capacity s3 s2 4 10 8 s1 t1 20 11 6 t3 t2**Max Concurrent Flow and Min Sparsest Cut**1 fi(e) : flow for pair i on edge e ifi(e) · c(e) for all e val(fi)¸¸ Di for all i max¸ (max concurrent flow) s3 s2 4 10 8 s1 t1 20 11 6 t3 t2**Max Concurrent Flow and Min Sparsest Cut**1 fi(e) : flow for pair i on edge e ifi(e) · c(e) for all e val(fi)¸¸ Di for all i max¸ (max concurrent flow) Sparsity of cut = capacity of cut / demand separated by cut Max Concurrent Flow ·Min Sparsity s3 s2 4 10 8 s1 t1 20 11 6 t3 t2**Flow-Cut Gap: Undir graphs**[Leighton-Rao’88] examples via expanders to show Max Throughput Flow ·O(1/log k) Min Multicut Max Concurrent Flow ·O(1/log k) Min Sparsity k = £(n2) in expander examples**Flow-Cut Gap: Undir graphs**[Leighton-Rao’88] for product multi-commodity flow Max Concurrent Flow ¸ (1/log k) Min Sparsity [Garg-Vazirani-Yannakakis’93] Max Throughput Flow ¸(1/log k) Min Multicut [Linial-London-Rabinovich’95,Aumann-Rabani’95] Max Concurrent Flow ¸ (1/log k) Min Sparsity**Flow-Cut Gap: Undir graphs Node Capacities**[Feige-Hajiaghayi-Lee’05] Max Concurrent Flow ¸ (1/log k) Min Sparsity [Garg-Vazirani-Yannakakis’93] Max Throughput Flow ¸(1/log k) Min Multicut**Flow-Cut Gap: Dir graphs**[Saks-Samorodnitsky-Zosin’04] Max Throughput Flow · O(1/k) Min Multicut [Chuzhoy-Khanna’07] Max Throughput Flow · O(1/n1/7) Min Multicut [Agrawal-Alon-Charikar’07] Max Throughput Flow ¸ (1/n11/23) Min Multicut ¸ 1/k Min Multicut (trivial)**Flow-Cut Gap: Dir graphs**Symmetric demands: (si,ti) and (ti,si) for each pair and cut has to separate only one of the two [Klein-Plotkin-Rao-Tardos’97] Max Throughput Flow ¸ (1/log2 k) Min Multicut Max Concurrent Flow ¸ (1/log3k) Min Sparsity [Even-Naor-Rao-Schieber’95] Max Throu. Flow ¸ (1/log n log log n) Min Multicut**Flow-Cut Gaps: Summary**k pairsin a graph G=(V,E) • £(log k) for undir graphs • Throughput Flow vsMulticut • Concurrent Flow vs Sparsest Cut • Node-capacited flows [Feige-Hajiaghayi-Lee’05] • O(polylog(k)) for dir graph with symmetric demands • Polynomial-factor lower bounds for dir graphs**Polymatroidal Networks**Capacity of edges incident to vjointly constrained by a polymatroid (monotone non-negsubmodular set func) e1 e2 e3 v e4 i2 S c(ei) · f(S) for every S µ {1,2,3,4}**Detour:Network Information Theory**Question: What is the information theoretic capacity of a network? Given G=(V,E) and pairs (s1,t1),...,(sk,tk) and rates/demands D1,...,Dk:can the pairs use the network to successfully transmit information at these rates? • Can use routing, (network) coding, and any other scheme ... • Network coding [Ahlswede-Cai-Li-Yeung’00]**Network Information Theory: Cut-Set Bound**Max Concurrent Rate · Min Sparsity S V\S**Network Information Theory**Max Concurrent Rate · Min Sparsity • In undirected graphs routing is near-optimal (within log factors). Follows from flow-cut gap upper bounds • In directed graphs routing can be very far from optimal • In directed graphs routing far from optimal even for multicast • Capacity of networks poorly understood**Capacity of wireless networks**Major issues to deal with: • interference due to broadcast nature of medium • noise**Capacity of wireless networks**Recent work: understand/model/approximate wireless networks via wirelinenetworks • Linear deterministic networks [Avestimehr-Diggavi-Tse’09] • Unicast/multicast (single source). Connection to polylinking systems and submodular flows [Goemans-Iwata-Zenklusen’09] • Polymatroidalnetworks [Kannan-Viswanath’11] • Multiple unicast.**Directed Polymatroidal Networks**[Lawler-Martel’82, Hassin’79] Directed graph G=(V,E) For each node v two polymatroids • ½v- with ground set ±- (v) • ½v+with ground set ±+(v) e 2 S f(e) ·½v- (S) for all S µ±-(v) e 2 S f(e) ·½v+ (S) for all S µ±+(v) v**s-t flow**Flow from s to t: “standard flow” with polymatroidal capacity constraints 1 2 2 1.2 3 3 1 s t 1.6 2 2 1**What is the cap. of a cut?**Assign each edge (a,b) of cut to either a or b Value = sum of function values on assigned sets Optimize over all assignments min{1+1+1, 1.2+1, 1.6+1} 1 2 2 1.2 3 3 1 s t 1.6 2 2 1**What is the cap. of a cut?**Other possibilities and why they don’t work • assign edges to both ends and take average • assign edges to both ends and take minimum**Maxflow-Mincut Theorem**[Lawler-Martel’82, Hassin’79] Theorem: In a directed polymatroidal network the max s-t flow is equal to the min s-t cut value. Model equivalent to submodular-flow model of[Edmonds-Giles’77] that can derive as special cases • polymatroid intersection theorem • maxflow-mincut in standard network flows • Lucchesi-Younger theorem**Undirected Polymatroidal Networks**“New” model: Undirected graph G=(V,E) For each node vsingle polymatroids • ½vwith ground set ±(v) e 2 S f(e) ·½v(S) for all S µ±(v) Note: maxflow-mincut does not hold, only within factor of 2! v**Why Undirected PolymatroidalNetworks?**• captures node-capacitated flows in undirected graphs • within factor of 2 approximates bi-directed polymatroidal networks relevant to wireless networks which have reciprocity • ability to use metric methods, large flow-cut gaps for multicommodity flows in directed networks**Multi-commodity Flows**Polymatroidal network G=(V,E) k pairs (s1,t1),...,(sk,tk) Multi-commodity flow: • fiissi-tiflow • f(e) = ifi(e) is total flow on e • flows on edges constrained by polymatroid constraints at nodes**Multi-commodity Cuts**Polymatroidal network G=(V,E) k pairs (s1,t1),...,(sk,tk) Multicut: set of edges that separates all pairs Sparsity of cut: cost of cut/demand separated by cut Cost of cut: as defined earlier via optimization**Main Results**• £(log k) flow-cut gap for undirpolymatroidal networks • throughput flow vsmulticut • concurrent flow vs sparsest cut • Directed graphs and symmetric demands • O(log2 k) flow-cut gap for throughput flow vsmulticut • O(log3 k) flow-cut gap for concurrent flow vs sparsest cut Flow-cut gap results match the known bounds for standard networks**Other Results**• O(√log k)-approximation in undirpolymatroidal networks for separators (via tool from [Arora-Rao-Vazirani’04]) • Two new proofs of maxflow-mincut theorem for s-t flow in polymatroidal networks • See paper ... • [C-Kannan-Viswanath’12] : O(1) gap for throughput flow vsmulticut in planar and minor-free graphs via KPR theorem**Implications for network information theory**[Kannan-Viswanath’11] + these results imply capacity of a class of wireless networks understood to within O(log k) factor for k-unicast**Local vs Global Polymatroid Constraints**A more general model: G=(V,E) graph f: 2E! R is a polymatroid on the set of edges f(S) is the total capacity of the set of edges S Function is global but problems become intractable [Jegelka-Bilmes’10,Svitkina-Fleischer’09]**Technical Ideas**• Directed polymatroidal networks: a reduction via uncrossing in the dual to standard edge-capacitated directed networks • Undirected polymatroidal networks: dual via Lovasz-extension • sparsest cut: round via line embeddingsinspired by [Feige-Hajiaghayi-Lee’05] on undir node-capacitated graphs • multicut: line embedding idea plus region growing [Leighton-Rao’88,Garg-Vazirani-Yannakakis’93]**Rest of talk**O(log k) upper bound on gap between max concurrent flow and min sparsity in undirpolymatroidal networks**Relaxation for Sparsest Cut**Want to find edge set E’ µ E to minimizecost(E’)/dem-sep(E’) Variables: x(e) whether e is cut or not y(i) whether pair siti is separated or not**Relaxation for Sparsest Cut**Relaxation for standard networks: min e c(e) x(e) iDi y(i) = 1 distx(si,ti) ¸ y(i) for all pairs i x, y¸ 0 Dual of LP for max concurrent flow**Relaxation for Sparsest Cut**Relaxation for polymatroidal networks: min cost of cut iDi y(i) = 1 distx(si,ti) ¸ y(i) for all pairs i x, y¸ 0**Modeling cost of cut**• Each cut edge uv has to be assigned to u or v • Introduce variables x(e,u) and x(e,v) for each edge uv • Add constraint x(e,u) + x(e,v) = x(e) • For a node v if S µ±(v) are cut edges assigned to v then cost at v is ½v(S)**Relaxation for Sparsest Cut**Relaxation for polymatroidal networks: min cost of cut iDi y(i) = 1 x(e,u) + x(e,v) = x(e) for each edge uv distx(si,ti) ¸ y(i) for all pairs i x, y¸ 0**Modeling cost of cut**• Each cut edge uv has to be assigned to u or v • Introduce variables x(e,u) and x(e,v) for each edge uv • Add constraint x(e,u) + x(e,v) = x(e) • For a node v if S µ±(v) are cut edges assigned to v then cost at v is ½v(S) • xvis the vector (x(e1,v),x(e2,v),...,x(eh,v)) where e1,e2,...,ehare edges in ±(v) • Use continuous extension ½*v(xv) to model ½v(S)**Relaxation for Sparsest Cut**Relaxation for polymatroidal networks: min v½*v(xv) iDi y(i) = 1 x(e,u) + x(e,v) = x(e) for each edge uv distx(si,ti) ¸ y(i) for all pairs i x, y¸ 0**Lovasz-extension of f**f*(x) = Eµ2 [0,1][ f(xµ) ] = s01f(xµ) dµ wherexµ = { i | xi¸µ } Example:x = (0.3, 0.1, 0.7, 0.2) xµ = {1,3} forµ = 0.21 andxµ = {3} forµ = 0.6 f*(x) = (1-0.7) f(;) + (0.7-0.3)f({3}) + (0.3-0.2) f({1,3}) + (0.2-0.1) f({1,3,4}) + (0.1-0) f({1,2,3,4}) 2 4 1 3 µ**Properties of f***• f* is convex ifff is submodular • Easy to evaluate f* • f*(x) = f-(x) for all x when f is submodular • If f is monotone and x·ythen f*(x) · f*(y)**Relaxation for Sparsest Cut**Relaxation for polymatroidal networks: min v½*v(xv) iDi y(i) = 1 x(e,u) + x(e,v) = x(e) for each edge uv distx(si,ti) ¸ y(i) for all pairs i x, y¸ 0 Lemma: Dual to LP for maximum concurrent flow**Rounding of Relaxation**Standard undirected networks: • Edge capacities: round via l1embedding[Linial-London-Rabinovich’95,Aumanna-Rabani’95] • Node-capacities: round via line embedding[Feige-Hajiaghayi-Lee’05]**Line Embeddings**[Matousek-Rabinovich’01] (V,d) metric space w(uv) non-neg weight for each uv g : V ! R is a line embedding with average weighted distortion ® ¸ 1 if • |g(u) – g(v)| · d(u,v) for all u,v (contraction) • uv w(uv) |g(u)-g(v)| ¸uv w(uv) d(uv)/®**Line Embeddings**[Matousek-Rabinovich’01] (V,d) metric space w(uv) non-neg weight for each uv g : V ! R is a line embedding with average weighted distortion ® if • |g(u) – g(v)| · d(u,v) for all u,v (contraction) • uv w(uv) |g(u)-g(v)| ¸uv w(uv) d(uv)/® Theorem [Bourgain]:Any metric space on n nodes admits line embedding with O(log n) average weighted distortion.**Rounding Algorithm**• Solve Lovasz-extension based convex relaxation • x(e) values induce metric on V • Embed metric into line with O(log n) average distortion w.r.t to weights w(uv) = D(uv) • Pick the best cut Sµamong all cuts on the line**Rounding Algorithm**• Solve Lovasz-extension based convex relaxation • x(e) values induce metric on V • Embed metric into line with O(log n) average distortion w.r.t to weights w(uv) = D(uv) • Pick the best cut Sµamong all cuts on the line • Remark: Clean algorithm that generalizes edge/node/polymatroid cases since cut is defined on edges though cost is more complex