Multicommodity flows and cuts in polymatroidal networks

Chandra Chekuri, Sreeram Kannan, Adnan Raja, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

We consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [Math. Oper. Res., 7 (1982), pp. 334-347] and Hassin [On Network Flows, Ph.D. dissertation, Yale University, New Haven, CT, 1978] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [Ann. Discrete Math., 1 (1977), pp. 185-204]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far we are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks. We also consider the notion of undirected polymatroidal networks and observe that they provide a natural way to generalize flows and cuts in edge and node capacitated undirected networks. We establish flow-cut gap results in several scenarios that have been previously considered in the standard network flow models where capacities are on the edges or nodes. Our results are based on analyzing the dual of the flow relaxations via continuous extensions of submodular functions, in particular, the Lovász extension. For directed graphs we rely on a simple yet useful reduction from polymatroidal networks to standard networks. For undirected graphs we rely on the interplay between the Lovász extension of a submodular function and line embeddings with low average distortion introduced by Matousek and Rabinovich [Israel J. Math., 123 (2001), pp. 285-301]; this connection is inspired by, and generalizes, the work of Feige, Hajiaghayi, and Lee on node-capacitated multicommodity flows and cuts. Our results have found applications in wireless network information flow [S. Kannan and P. Viswanath, IEEE Trans. Inform. Theory, 60 (2014), pp. 6303-6328] and we anticipate others in the future.

Original languageEnglish (US)
Pages (from-to)912-943
Number of pages32
JournalSIAM Journal on Computing
Volume44
Issue number4
DOIs
StatePublished - Jan 1 2015

Fingerprint

Multicommodity Flow
Wireless networks
Directed graphs
Network Flow
Submodular Function
Information Flow
Vertex of a graph
Wireless Networks
Continuous Extension
Min-cut
Generalise
Capacity Constraints
Undirected Graph
Directed Graph
Scenarios
Line
Theorem
Model

Keywords

  • Flow-cut gap
  • Line embedding
  • Multicommodity flow
  • Polymatroidal network

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Cite this

Multicommodity flows and cuts in polymatroidal networks. / Chekuri, Chandra; Kannan, Sreeram; Raja, Adnan; Viswanath, Pramod.

In: SIAM Journal on Computing, Vol. 44, No. 4, 01.01.2015, p. 912-943.

Research output: Contribution to journalArticle

Chekuri, Chandra ; Kannan, Sreeram ; Raja, Adnan ; Viswanath, Pramod. / Multicommodity flows and cuts in polymatroidal networks. In: SIAM Journal on Computing. 2015 ; Vol. 44, No. 4. pp. 912-943.
@article{ea447dc6ba9f41f9885af39b530e1194,
title = "Multicommodity flows and cuts in polymatroidal networks",
abstract = "We consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [Math. Oper. Res., 7 (1982), pp. 334-347] and Hassin [On Network Flows, Ph.D. dissertation, Yale University, New Haven, CT, 1978] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [Ann. Discrete Math., 1 (1977), pp. 185-204]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far we are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks. We also consider the notion of undirected polymatroidal networks and observe that they provide a natural way to generalize flows and cuts in edge and node capacitated undirected networks. We establish flow-cut gap results in several scenarios that have been previously considered in the standard network flow models where capacities are on the edges or nodes. Our results are based on analyzing the dual of the flow relaxations via continuous extensions of submodular functions, in particular, the Lov{\'a}sz extension. For directed graphs we rely on a simple yet useful reduction from polymatroidal networks to standard networks. For undirected graphs we rely on the interplay between the Lov{\'a}sz extension of a submodular function and line embeddings with low average distortion introduced by Matousek and Rabinovich [Israel J. Math., 123 (2001), pp. 285-301]; this connection is inspired by, and generalizes, the work of Feige, Hajiaghayi, and Lee on node-capacitated multicommodity flows and cuts. Our results have found applications in wireless network information flow [S. Kannan and P. Viswanath, IEEE Trans. Inform. Theory, 60 (2014), pp. 6303-6328] and we anticipate others in the future.",
keywords = "Flow-cut gap, Line embedding, Multicommodity flow, Polymatroidal network",
author = "Chandra Chekuri and Sreeram Kannan and Adnan Raja and Pramod Viswanath",
year = "2015",
month = "1",
day = "1",
doi = "10.1137/130906830",
language = "English (US)",
volume = "44",
pages = "912--943",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "4",

}

TY - JOUR

T1 - Multicommodity flows and cuts in polymatroidal networks

AU - Chekuri, Chandra

AU - Kannan, Sreeram

AU - Raja, Adnan

AU - Viswanath, Pramod

PY - 2015/1/1

Y1 - 2015/1/1

N2 - We consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [Math. Oper. Res., 7 (1982), pp. 334-347] and Hassin [On Network Flows, Ph.D. dissertation, Yale University, New Haven, CT, 1978] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [Ann. Discrete Math., 1 (1977), pp. 185-204]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far we are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks. We also consider the notion of undirected polymatroidal networks and observe that they provide a natural way to generalize flows and cuts in edge and node capacitated undirected networks. We establish flow-cut gap results in several scenarios that have been previously considered in the standard network flow models where capacities are on the edges or nodes. Our results are based on analyzing the dual of the flow relaxations via continuous extensions of submodular functions, in particular, the Lovász extension. For directed graphs we rely on a simple yet useful reduction from polymatroidal networks to standard networks. For undirected graphs we rely on the interplay between the Lovász extension of a submodular function and line embeddings with low average distortion introduced by Matousek and Rabinovich [Israel J. Math., 123 (2001), pp. 285-301]; this connection is inspired by, and generalizes, the work of Feige, Hajiaghayi, and Lee on node-capacitated multicommodity flows and cuts. Our results have found applications in wireless network information flow [S. Kannan and P. Viswanath, IEEE Trans. Inform. Theory, 60 (2014), pp. 6303-6328] and we anticipate others in the future.

AB - We consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [Math. Oper. Res., 7 (1982), pp. 334-347] and Hassin [On Network Flows, Ph.D. dissertation, Yale University, New Haven, CT, 1978] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [Ann. Discrete Math., 1 (1977), pp. 185-204]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far we are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks. We also consider the notion of undirected polymatroidal networks and observe that they provide a natural way to generalize flows and cuts in edge and node capacitated undirected networks. We establish flow-cut gap results in several scenarios that have been previously considered in the standard network flow models where capacities are on the edges or nodes. Our results are based on analyzing the dual of the flow relaxations via continuous extensions of submodular functions, in particular, the Lovász extension. For directed graphs we rely on a simple yet useful reduction from polymatroidal networks to standard networks. For undirected graphs we rely on the interplay between the Lovász extension of a submodular function and line embeddings with low average distortion introduced by Matousek and Rabinovich [Israel J. Math., 123 (2001), pp. 285-301]; this connection is inspired by, and generalizes, the work of Feige, Hajiaghayi, and Lee on node-capacitated multicommodity flows and cuts. Our results have found applications in wireless network information flow [S. Kannan and P. Viswanath, IEEE Trans. Inform. Theory, 60 (2014), pp. 6303-6328] and we anticipate others in the future.

KW - Flow-cut gap

KW - Line embedding

KW - Multicommodity flow

KW - Polymatroidal network

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

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

U2 - 10.1137/130906830

DO - 10.1137/130906830

M3 - Article

AN - SCOPUS:84940650320

VL - 44

SP - 912

EP - 943

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 4

ER -