English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider multicommodity flow and cut problems in {\em polymatroidal}networks where there are submodular capacity constraints on the edges incidentto a node. Polymatroidal networks were introduced by Lawler and Martel andHassin in the single-commodity setting and are closely related to thesubmodular flow model of Edmonds and Giles; the well-known maxflow-mincuttheorem holds in this more general setting. Polymatroidal networks for themulticommodity case have not, as far as the authors are aware, been previouslyexplored. Our work is primarily motivated by applications to information flowin wireless networks. We also consider the notion of undirected polymatroidalnetworks and observe that they provide a natural way to generalize flows andcuts in edge and node capacitated undirected networks.  We establish poly-logarithmic flow-cut gap results in several scenarios thathave been previously considered in the standard network flow models wherecapacities are on the edges or nodes. Our results have already foundaplications in wireless network information flow and we anticipate more in thefuture. On the technical side our key tools are the formulation and analysis ofthe dual of the flow relaxations via continuous extensions of submodularfunctions, in particular the Lov\'asz extension. For directed graphs we rely ona simple yet useful reduction from polymatroidal networks to standard networks.For undirected graphs we rely on the interplay between the Lov\'asz extensionof a submodular function and line embeddings with low average distortionintroduced by Matousek and Rabinovich; this connection is inspired by, andgeneralizes, the work of Feige, Hajiaghayi and Lee on node-capacitatedmulticommodity flows and cuts. The applicability of embeddings to polymatroidalnetworks is of independent mathematical interest.

Multicommodity Flows and Cuts in Polymatroidal Networks