DIMACS Theory Seminar


"Multicommodity Flows: A Survey of Recent Research"


Tom Leighton
Math Dept. and Lab for Computer Science, MIT


Lunch 11:45 AM, Room 402, Computer Science Building
Talk will be held in the Small Auditorium, Room 105, 12 Noon
Princeton University


Lunch 11:45 AM, Talk 12 Noon
Tuesday, March 28, 1995


The multicommodity flow problem consists of shipping a collection of different commodites through a common network so that the total flow going through each edge in the network does not exceed its capacity. Multicommodity flow problems arise in a wide variety of applications and have been extensively studied during the past several decades.

In the talk, we will survey recent work on improved algorithms for the multicommodity flow problem. Particular emphasis will be placed on approximation algorithms that can compute near optimal flow paths in a relatively small amount of time. A new and very simple local-control algorithm for multicommodity flow will also be presented. The latter algorithm is notable in that it does not rely on augmenting paths, shortest paths, min-cost paths, or similar techniques to push flow through the network. As a consequence, the algorithm is particularly well-suited for applications involving distributed networks.

We will also breifly mention recent work on the development of a max-flow/min-cut theorem for multicommodity flows.

The talk will be introductory in nature.

Document last modified on March 7, 1995