Report Number: CS-TR-99-1622
Institution: Stanford University, Department of Computer Science
Title: Multicommodity and Generalized Flow Algorithms: Theory and
Practice
Author: Oldham, Jeffrey David
Date: August 1999
Abstract: We present several simple, practical, and fast algorithms for
linear programs, concentrating on network flow problems.
Since the late 1980s, researchers developed different
combinatorial approximation algorithms for fractional packing
problems, obtaining the fastest theoretical running times to
solve multicommodity minimum-cost and concurrent flow
problems. A direct implementation of these multicommodity
flow algorithms was several orders of magnitude slower than
solving these problems using a commercial linear programming
solver. Through experimentation, we determined which
theoretically equivalent constructs are experimentally
efficient. Guided by theory, we designed and implemented
practical improvements while maintaining the same worst-case
complexity bounds. The resulting algorithms solve problems
orders of magnitude faster than commercial linear programming
solvers and problems an order of magnitude larger.
We also present simple, combinatorial algorithms for
generalized flow problems. These problems generalize ordinary
network flow problems by specifying a flow multiplier \mu(a)
for each arc a. Using multipliers permit a flow problem to
model transforming one type into another, e.g., currency
exchange, and modification of the amount of flow, e.g., water
evaporation from canals or accrual of interest in bank
accounts. First, we show the generalized shortest paths
problem can be solved using existing network flow ideas,
i.e., by combining the Bellman-Ford-Moore shortest path
framework and Megiddo's parametric search. Second, we combine
this algorithm with fractional packing frameworks to yield
the first polynomial-time combinatorial approximation
algorithms for the generalized versions of the
nonnegative-cost minimum-cost flow, concurrent flow,
multicommodity maximum flow, and multicommodity
nonnegative-cost minimum-cost flow problems. These algorithms
show that generalized concurrent flow and multicommodity
maximum flow have strongly polynomial approximation
algorithms.
http://i.stanford.edu/pub/cstr/reports/cs/tr/99/1622/CS-TR-99-1622.pdf