About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.