MIT Department of Electrical Engineering & Computer Science

MIT TOC SEMINAR

Tuesday, October 25, 1994

Refreshments at 4:00pm, Talk at 4:15pm

NE43-3rd Floor Lounge

The Quickest Transshipment Problem

by Eva Tardos, Cornell University

ABSTRACT

A bomb explodes beneath a skyscraper. Occupants flee their offices and rush to the exits. An optimal evacuation plan specifies exactly how the occupants can reach safety in the minimum overall time. Devising an optimal evacuation plan is a difficult problem; we describe the first polynomial time algorithm for this problem.

Evacuation can be modeled by dynamic network flows, a generalization of network flows introduced by Ford and Fulkerson that takes into acount the time required to traverse the edges. Dynamic network flows have been studied extensively, and have numerous applications; in some of these, the capacities are small integers and it is important to find integral flows. There are no polynomial-time algorithms known for most versions of the problem.

In this paper we talk the first polynomial-time algorithm for the integral evacuation problem, or more generally the quickest transshipment problem. Previously, the integral evacuation problem could only be solved efficiently in the special case of a single source.

Joint work with Bruce Hoppe.

Host: Silvio Micali