The maximum flow problem and its dual, the minimum cut problem, are used in many applications. Algorithms for this fundamental problem have been extensively studied for half a century by Combinatorial Optimization, Operations Research, and Computer Science communities. However, both theoretical and practical advances are still being made in the area.
In this talk we discuss two such advances.
First we introduce the partial augment--relabel algorithm, which is a variation of the push--relabel method, and show that it exhibits promising performance in practice. Then we describe an algorithm based on non-unit length functions. This algorithm has very good theoretical bounds. We conclude with a discussion of what it would take to make the length function idea perform robustly in practice.
Copyright. All Rights Reserved.