An auction algorithm for the max-flow problem

We propose a new algorithm for the max-flow problem. It consists of a sequence of augmentations along paths constructed by an auction-like algorithm. These paths are not necessarily shortest, that is, they need not contain a minimum number of arcs. However, they can be found typically with much less computation than the shortest augmenting paths used by competing methods. Our algorithm outperforms these latter methods as well as state-of-the-art preflow-push algorithms by a very large margin in tests with standard randomly generated problems.This paper is a substantially revised version of Ref. 1.Many thanks are due to David Castanon and Paul Tseng for several helpful comments. The suggestions of the referees were also appreciated. David Castanon, Lakis Polymenakos, and Won-Jong Kim helped with some of the computational experimentation. This research was supported by NSF under Grant CCR-9103804.