[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

COMPUTER SCIENCE

The University of Chicago

THEORY SEMINAR

_____________________

Date:		Wednesday, February 15, 2012

Time:		3 p.m.

Place:		Ryerson 251, 1100 E. 58th Street

_______________________

Speaker:	Chandra Chekuri

From:		University of Illinois, Urbana-Champaign

Title: 	        Multicommodity Flows and Cuts in Polymatroidal Networks
 
Abstract:		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 heorem 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. 

*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120214/ccec6cd7/attachment.htm