6.7.2.3. Final Running Time Analysis

To show a strongly polynomial bound on the running time of the minimum mean cycle cancelling algorithm, we need the following ideas: Consider an arbitrary flow \(f^{(i)}\) and a tight potential function \(\pi\) for \(f^{(i)}\). Any edge whose reduced cost \(c^\pi_{x,y}\) has an absolute value sufficiently larger than \(\epsilon_{f^{(i)}}\) is fixed in the sense that every flow \(f\) with \(\epsilon_f \le \epsilon_{f^{(i)}}\) satisfies \(f_{x,y} = f^{(i)}_{x,y}\). In particular, every optimal flow sends exactly \(f^{(i)}_{x,y}\) units of flow along the edge \((x, y)\). Lemma 6.40 below makes this precise. Lemma 6.41 below shows that, for all \(0 \le i \le t - nm \lg n\), there exists at least one edge \((x, y)\) that is fixed by \(f^{(i + nm \lg n)}\) but not by \(f^{(i)}\). Thus, \(f^{(i + nm \lg n)}\) has strictly more fixed edges than \(f^{(i)}\). Since \(f^{(t-1)}\) cannot fix all edges of \(G\) because the \((t-1)\)st iteration changes the flow along at least one edge of \(G\), \(f^{(t-1)}\) fixes at most \(m-1\) edges. Thus, \(t - 1 < nm^2 \lg n\), that is, the minimum mean cycle cancelling algorithm terminates after at most \(t + 1 \le nm^2 \lg n\) iterations and thus has running time \(O(n^2 m^3 \lg n)\).

Lemma 6.40: Let \(f\) and \(f'\) be two flows such that \(\epsilon_{f'} \le \epsilon_f\) and \(\epsilon_f > 0\), and let \(\pi\) be a tight potential function for \(f\). If \(|c^\pi_{x, y}| \ge 2n \epsilon_f\) for any edge \((x, y) \in G\), then \(f'_{x,y} = f_{x,y}\).

Proof: First assume that \(c^\pi_{x,y} \ge 2n \epsilon_f > \epsilon_f\). Then, by the first \(\epsilon\)-optimality condition, \(f_{x,y} = 0\). Suppose that there exists a flow \(f'\) with \(\epsilon_{f'} \le \epsilon_f\) and such that \(f'_{x,y} > 0\).

Since both \(f\) and \(f'\) are flows, Lemma 6.6 shows that the pseudo-flow \(\delta\) defined as \(\delta_{x,y} = \max(0, f'_{x,y} - f'_{y,x} - f_{x,y} + f_{y,x})\) is a circulation in \(G^f\). By Lemma 6.5, \(\delta\) can be written as the sum of cycle flows \(\delta^{(1)}, \ldots, \delta^{(s)}\) in \(G^f\).

Since \(f_{x,y} = 0\) and \(f'_{x,y} > 0\), we must have \(\delta^{(i)}_{x,y} > 0\) for some \(1 \le i \le s\). Let \(D^{(i)}\) be the cycle along which \(\delta^{(i)}\) sends flow. Every edge \((w, z) \in D^{(i)}\) is in \(G^f\).

If \((w, z) \in G\), then \(f_{w,z} < u_{w,z}\), so the second \(\epsilon\)-optimality condition implies that \(c^\pi_{w,z} \ge -\epsilon_f\).

If \((w, z) \notin G\), then \((z, w) \in G\) and \(f_{z, w} > 0\) because \((w, z) \in G^f\). Thus, by the first \(\epsilon\)-optimality condition, \(c^\pi_{z, w} \le \epsilon_f\), that is, once again, \(c^\pi_{w, z} \ge -\epsilon_f\).

This shows that the cost of the cycle \(D^{(i)}\) is at least \(c^\pi_{x,y} - \epsilon_f(|D^{(i)}| - 1) > 2n \epsilon_f - n \epsilon_f = n\epsilon_f\).

By Lemma 6.8, the flow \(\bigl(\delta^{(i)}\bigr)^r\) is a cycle flow in \(G^{f'}\). Since the cost of \(D^{(i)}\) is greater than \(n\epsilon_f\), the cycle \(\bigl(D^{(i)}\bigr)^r\) that contains all edges \(e \in G^{f'}\) with \(\bigl(\delta^{(i)}\bigr)^r_e > 0\) has cost less than \(-n\epsilon_f\). Thus, its mean cost is less than \(-\epsilon_f \le -\epsilon_f'\).

However, \(\mu^*_{f'} = -\epsilon_{f'}\), by Lemma 6.34, that is, \(G^{f'}\) has no cycle of mean cost less than \(-\epsilon_f'\), a contradiction.

If \(c^\pi_{u, v} \le -2n \epsilon_f\), then \(f_{x,y} = u_{x,y}\), by the second \(\epsilon\)-optimality condition. An analogous analysis to the previous case shows that \(f'_{x,y} = u_{x,y}\) in this case. ▨

The next lemma now states that at least every \(nm \lg (2n)\) iterations, a new edges gets fixed.

Lemma 6.41: For every \(0 \le i \le t - nm \lg (2n)\), there exists an edge \((x, y)\) such that \(f^{(i + nm \lg (2n))}_{x,y} = \cdots = f^{(t)}_{x,y}\) but \(f^{(i)}_{x,y} \ne f^{(j)}_{x,y}\) for some \(i < j \le t\).

Proof: For notational convenience, let \(f = f^{(i)}\), \(f' = f^{(i + nm \lg (2n))}\), \(\epsilon = \epsilon_f\), and \(\epsilon' = \epsilon_{f'}\). Let \(\pi'\) be a tight potential function for \(f'\). By Lemma 6.37, we have

\[\epsilon' \le \epsilon\Bigl(1 - \frac{1}{n}\Bigr)^{n \lg (2n)} \le \epsilon e^{-\lg (2n)} < \frac{\epsilon}{2n}.\]

Let \(C^{(i)}\) be the negative-cost cycle in \(G^{f^{(i)}}\) cancelled to produce \(f^{(i+1)}\) from \(f^{(i)}\). Since \(\mu^*_{f^{(i)}} = -\epsilon_{f^{(i)}} = -\epsilon\) and \(C^{(i)}\) is a minimum mean cost cycle in \(G^{f^{(i)}}\), the mean cost of \(C^{(i)}\) is \(-\epsilon\). Since the mean cost and the mean reduced cost of any cycle with respect to any potential function are the same, the mean reduced cost of \(C^{(i)}\) with respect to the potential function \(\pi'\) is also \(-\epsilon\). Thus, \(C^{(i)}\) contains an edge \(e\) with \(c^{\pi'}_e \le -\epsilon < -2n\epsilon'\). By Lemma 6.40, we thus have \(f'_e = f^{(i + nm \lg(2n))}_e = \cdots = f^{(t)}_e\). On the other hand, \(f_e = f^{(i)}_e \ne f^{(i+1)}_e\) because \(e \in C^{(i)}\). ▨

The following theorem now summarizes the discussion in this chapter:

Theorem 6.42: The minimum mean cycle cancelling algorithm takes \(O\bigl(n^2m^3\lg n\bigr)\) time to compute a minimum-cost flow in any network.

Proof: We argued above that Lemma 6.41 implies that the algorithm has \(O\bigl(nm^2 \lg n\bigr)\) iterations. By Lemma 6.30, each iteration takes \(O(nm)\) time. Thus, the algorithm takes \(O\bigl(n^2m^3\lg n\bigr)\) time. Since the algorithm is a variant of the negative cycle cancelling algorithm, its correctness follows from the correctness argument in Section 6.4. ▨