The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem
Abstract
We introduce an algorithm that solves the maximum flow problem without
generating flows explicitly.
The algorithm solves directly a problem we call the
maximum s-excess problem. That problem is equivalent to the minimum
cut problem, and is a direct extension of the maximum closure problem.
A new certificate of optimality and a novel solution approach were
motivated by Lerchs
and Grossman's algorithm [LG64] for maximum closure described in
[Hoc96]. The concepts used also lead to a new
parametric analysis algorithm generating all breakpoints in the
amount of time of a single run.
The insights derived from the analysis of the new
algorithm lead to a new simplex algorithm for the maximum flow
problem. We show that the new simplex algorithm
can perform a parametric analysis
in the same amount of time as a single run. This is the first known
simplex algorithm for maximum flow that generates all possible
breakpoints of parameter values in the same complexity as required to
solve a single maximum flow instance and the fastest one.
The complexities of our pseudoflow algorithm, the new simplex algorithm, and
the parametric analysis for both algorithms are O(mn logn) on a graph with n nodes
and m arcs.
Download Information
Click on the following title to view and download the paper in PostScript format.
- The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem (14 pages, 202 KB)
,
- Dorit S. Hochbaum. Proceedings of Integer
Programming and Combinatorial Optimization, 6th International IPCO conference, Houston Texas, June 1998, 325-337.
dorit@hochbaum.ieor.berkeley.edu
7/30/98