JavaScript is disabled for your browser. Some features of this site may not work without it.
Efficient Dynamic Network Flow Algorithms

Author
Hoppe, Bruce
Abstract
Dynamic network flows model transportation. A dynamic network
consists of a graph with capacities and transit times on its
edges. Flow moves through a dynamic network over time. Edge
capacities restrict the rate of flow and edge transit times
determine how long each unit of flow spends traversing the network.
Dynamic network flows have been studied extensively for decades.
This thesis introduces the first polynomial algorithms to solve
several important dynamic network flow problems. We solve them
by computing chain-decomposable flows, a new class of structured
dynamic flows.
We solve the quickest transshipment problem. An instance of this
problem consists of a dynamic network with several sources and
sinks. Each source has a specified supply and each sink a
specified demand of flow. The goal is to move the appropriate
amount of flow out of each source and into each sink within the
least overall time. Previously, this problem could only be
solved efficiently in the special case of a single source and
single sink.
Our quickest transshipment algorithm depends on efficient
solutions to the dynamic transshipment problem and the
lexicographically maximum dynamic flow problem. The former is a
version of the quickest transshipment problem in which the time
bound is specified. The latter is a maximum flow problem in a
dynamic network with prioritized sources and sinks; the goal is
to maximize the amount of flow leaving each high-priority subset
of sources and sinks.
We also consider the universally maximum dynamic flow problem. A
universally maximum dynamic flow sends flow between a source and
sink so that the sink receives flow as quickly as possible;
subject to that, the source releases flow as late as possible.
We describe the first polynomial algorithm
to approximate a universally maximum dynamic flow within
a factor of $(1+\eps)$, for any $\eps>0$.
We also describe the first polynomial
algorithm to compute the value of a universally maximum dynamic
flow at a single specified moment of time.
Date Issued
1995-06Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR95-1524
Type
technical report