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