6.7. Minimum Mean Cycle Cancelling*

The minimum mean cycle cancelling algorithm is easy to describe: Recall the negative cycle cancelling algorithm from Section 6.4.

Let the mean cost of a cycle \(C\) in \(G^f\) be defined as

\[\mu_C = \sum_{e \in C} \frac{c^f_e}{|C|},\]

that is, \(\mu_C\) is equal to the average residual cost of the edges in \(C\).

Let

\[\mu^*_f = \min_C \mu_C,\]

where the minimum is taken over all cycles in \(G^f\).

We call a cycle \(C\) that satisfies \(\mu_C = \mu^*_f\) a minimum mean cost cycle in \(G^f\).

The only change we make to turn the negative cycle cancelling algorithm into the minimum mean cycle cancelling algorithm is to choose the cycle to cancel in each iteration to be a minimum mean cost cycle.

Note that the mean cost of a cycle is negative if and only if the cycle is a negative cycle. Thus, if \(\mu^*_f \ge 0\), then \(G^f\) has no negative cycle, which implies that \(f\) is a minimum-cost flow, by Lemma 6.3. Just as the negative cycle cancelling algorithm, the algorithm terminates in this case.

If \(\mu^*_f < 0\), we find a minimum mean cost cycle \(C\) and push flow along \(C\) as in the standard negative cycle cancelling algorithm and then start another iteration. Quite surprisingly, this strategy of picking a negative cycle to cancel is sufficient to obtain a running time independent of the edge costs and capacities. While this description of the minimum mean cycle cancelling algorithm is simple, proving that it achieves a running time independent of the edge capacities and edge costs requires some effort, as we will see.

As in Sections 6.5 and 6.6, we assume that there exists an uncapacitated path between every pair of vertices in \(G\).