6.7.2.2. Preliminary Analysis for Integer Costs

The final ingredient for a preliminary analysis of the minimum mean cycle cancelling algorithm is the following lemma, which shows that, once \(\epsilon_f\) is small enough, it is in fact zero, provided that all edge costs are integers:

Lemma 6.38: If all edge costs are integers and \(\epsilon_f < \frac{1}{n}\), then \(f\) is a minimum-cost flow.

Proof: Since the edge costs are integers, every negative-cost cycle in \(G^f\) has cost at most \(-1\). Since this cycle has at most \(n\) vertices, its mean cost is thus at most \(-\frac{1}{n}\). This shows that, as long as there exists a negative-cost cycle, we have \(\mu_f \le -\frac{1}{n}\), that is, \(\epsilon_f \ge \frac{1}{n}\), by Lemma 6.34. Thus, if \(\epsilon_f < \frac{1}{n}\), there does not exist any negative-cost cycle in \(G^f\), that is, \(f\) is a minimum-cost flow, by Lemma 6.3. ▨

Using Lemmas 6.37 and 6.38, we can prove the following preliminary bound on the running time of the minimum mean cycle cancelling algorithm:

Theorem 6.39: The mimimum mean cycle cancelling algorithm takes \(O\bigl(n^2m^2\lg(nC)\bigr)\) time to compute a minimum-cost flow in a network whose edges have integer costs between \(-C\) and \(C\).

Proof: Since each iteration takes \(O(nm)\) time, by Lemma 6.30, the running time follows if we can prove that the algorithm runs for \(t = O(nm\lg(nC))\) iterations. Since every edge has cost between \(-C\) and \(C\), the initial flow \(f^{(0)}\) satisfies \(\epsilon_{f^{(0)}} \le C\). By Lemma 6.38, the penultimate flow \(f^{(t-1)}\) satisfies \(\epsilon_{f^{(t-1)}} \ge \frac{1}{n}\) because \(G^{f^{(t-1)}}\) contains a negative cycle. By Lemma 6.37, we have \(\epsilon_{f^{(i+m)}} \le \bigl(1 - \frac{1}{n}\bigr)\epsilon_{f^{(i)}}\) for all \(0 \le i \le t - m\). Thus,

\[\epsilon_{f^{(t-1)}} \le \left(1 - \frac{1}{n}\right)^{\lfloor (t-1)/m \rfloor}\epsilon_{f^{(0)}},\]

that is,

\[\frac{1}{nC} \le \frac{\epsilon_{f^{(t-1)}}}{\epsilon_{f^{(0)}}} \le \left(1 - \frac{1}{n}\right)^{\lfloor (t - 1)/m \rfloor} \le \left(1 - \frac{1}{n}\right)^{(t - m)/m}.\]

Next observe that \(\bigl(1 - \frac{1}{n}\bigr)^n \le \frac{1}{e}\), so

\[\frac{1}{nC} \le \left(1 - \frac{1}{n}\right)^{(t - m)/m} \le \left(\frac{1}{e}\right)^{(t - m) / nm}\]

or

\[nC \ge e^{(t - m)/nm}.\]

Taking the logarithm and multiplying with \(nm\), gives \(nm \ln (nC) \ge t - m\). Thus, \(t \le nm \ln (nC) + m = O(nm \lg (nC))\). ▨