More pathological examples for network flow problems

Abstract

Two examples are presented. The first example is "bad" for a large subset of the "primal" minimum cost flow algorithms, namely those algorithms which start with the required amount of s - t flow distributed in a feasible, but nonoptimal manner, and which get optimal by sending flow about negative cycles. In particular, the example is bad for the "primal" method which always sends flow about a cycle which yields the largest decrease in the objective function. The second example requires O(n3) flow augmentations using tie-breaking variants of either the Edmonds-Karp shortest path or fewest reverse arcs in path maximum flow algorithms. This example implies that it is not possible to substantially improve the performance (in a worst case sense) of either algorithm by resolving ties. © 1973 The Mathematical Programming Society.