The well-known maxflow-mincut theorem for single-commodity flows in directed networks is of fundmental importance in combinatorial optimization. Flow-cut equivalence breaks down in the multicommodity case and a substantial amount of research in the algorithms community has focused on understanding the gap between multicommodity flows and associated cuts. Poly-logarithmic gap results have been established in various settings via tools from network decomposition and metric embeddings.

In this talk we describe work on obtaining flow-cut gap results in *polymatroidal* networks. In these networks there are submodular capacity constraints on the edges incident to a node. Such networks were introduced by Lawler and Martel and Hassin in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles. The well-known maxflow-mincut theorem for a single-commodity holds in polymatroidal networks however the the multicommodity case has not been previously explored. Our work is primarily motivated by applications to information flow in wireless networks, however, the technical results we obtain are of independent mathematical interest as they generalize known results in standard networks and point to the utility of the notion of line embeddings suggested by Matousek and Rabinovich.

Joint work with Sreeram Kannan, Adnan Raja and Pramod Viswanath from UIUC ECE Department.