Report Number: CS-TR-97-1600
Institution: Stanford University, Department of Computer Science
Title: An Implementation of a Combinatorial Approximation Algorithm
for Minimum-Cost Multicommodity Flow
Author: Goldberg, Andrew
Author: Oldham, Jeffrey D.
Author: Plotkin, Serge
Author: Stein, Cliff
Date: December 1997
Abstract: The minimum-cost multicommodity flow problem involves
simultaneously shipping multiple commodities through a single
network so that the total flow obeys arc capacity constraints
and has minimum cost.
Multicommodity flow problems can be expressed as linear
programs, and most theoretical and practical algorithms use
linear-programming algorithms specialized for the problems'
structures. Combinatorial approximation algorithms yield
flows with costs slightly larger than the minimum cost and
use capacities slightly larger than the given capacities.
Theoretically, the running times of these algorithms are much
less than that of linear-programming-based algorithms.
We combine and modify the theoretical ideas in these
approximation algorithms to yield a fast, practical
implementation solving the minimum-cost multicommodity flow
problem. Experimentally, the algorithm solved our problem
instances (to 1% accuracy) two to three orders of magnitude
faster than the linear-programming package CPLEX and the
linear-programming based multicommodity flow program PPRN.