6.7.2.1. Decreasing Minimum Mean Costs

In this section, we prove that the minimum mean cost \(\mu^*_f\) of the cycles in \(G^f\) does not decrease over the course of the algorithm and that this cost actually decreases from time to time.

Recall the characterization of a minimum-cost flow in Lemma 6.1 based on complementary slackness. The following is a relaxation of these complementary slackness conditions.

A flow \(f\) is \(\boldsymbol{\epsilon}\)-optimal if there exists a potential function \(\pi\) such that every edge \((x, y) \in G\) satisfies

• \(f_{x,y} = 0\) if \(c^\pi_{x,y} > \epsilon\) and
• \(f_{x,y} = u_{x,y}\) if \(c^\pi_{x,y} < -\epsilon\).

We refer to the minimum value of \(\epsilon\) for which \(f\) is \(\epsilon\)-optimal as \(\epsilon_f\).

We call a potential function that shows that \(f\) is \(\epsilon_f\)-optimal a tight potential function for \(f\).

In other words, a flow \(f\) is a minimum-cost flow if and only if it is \(0\)-optimal. A flow \(f\) with \(\epsilon_f > 0\) is not a minimum-cost flow, but \(\epsilon_f\) provides a measure of how far away from optimality \(f\) is.

The next lemma shows that the mean cost \(\mu^*_f\) of a minimum mean cost cycle in \(G^f\) measures the optimality \(\epsilon_f\) of \(f\):

Lemma 6.34: For any flow \(f\), \(\epsilon_f = -\mu^*_f\).

Proof: To prove that \(\epsilon_f \ge -\mu^*_f\), let \(\pi\) be a tight potential function for \(f\) and consider any edge \((x, y) \in G^f\). Then \(u^f_{x,y} > 0\). Thus, \((x, y) \in G\) and \(f_{x,y} < u_{x,y}\), or \((y, x) \in G\) and \(f_{y,x} > 0\).

If \(f_{x,y} < u_{x,y}\), then \(c^\pi_{x,y} \ge -\epsilon_f\), by the second \(\epsilon\)-optimality condition.

If \(f_{y,x} > 0\), then \(c^\pi_{y,x} \le \epsilon_f\), by the first \(\epsilon\)-optimality condition, and thus, again, \(c^\pi_{x,y} = -c^\pi_{y,x} \ge -\epsilon_f\).

Since every edge has reduced cost at least \(-\epsilon_f\) and the cost of any cycle equals its reduced cost, this shows that the mean cost of any cycle is at least \(-\epsilon_f\), that is, \(\mu^*_f \ge -\epsilon_f\).

To prove that \(\epsilon_f \le -\mu^*_f\), let \(c^r_{x,y} = c^f_{x,y} - \mu^*_f\), for all \((x, y) \in G^f\). Then every cycle in \(G_f\) has non-negative mean cost with respect to \(c^r\) because every cycle has mean cost at least \(\mu^*_f\) with respect to \(c^f\) and the cost of every edge—and thus the mean cost of every cycle—is reduced by \(\mu^*_f\) when using \(c^r\) instead of \(c^f\). Thus, we can compute the distance \(d_x\) from some vertex \(s\) to every vertex \(x \in V\) with respect to these costs \(c^r\) and define \(\pi_x = -d_x\) for every vertex \(x \in V\). This gives

\[c^\pi_{x,y} = c^f_{x,y} - \pi_x + \pi_y = c^f_{x,y} + d_x - d_y = c^r_{x,y} + d_x - d_y + \mu^*_f \ge \mu^*_f\]

for every edge \((x, y) \in G^f\), because \(d_y \le d_x + c^r_{x,y}\) for every edge \((x, y) \in G^f\).

This implies that \(f\) is \(-\mu^*_f\)-optimal, that is, that \(\epsilon_f \le -\mu^*_f\). Indeed, for any edge \((x, y) \in G\), if \(c^\pi_{x,y} > -\mu^*_f\), then \(c^\pi_{y,x} < \mu^*_f\), so \((y, x) \notin G^f\), that is, \(f_{x,y} = 0\). This proves the first \(\epsilon\)-optimality condition for \(\epsilon = -\mu^*_f\). If \(c^\pi_{x,y} < \mu^*_f\), then \((x, y) \notin G^f\), that is, \(f_{x,y} = u_{x,y}\). This proves the second \(\epsilon\)-optimality condition for \(\epsilon = -\mu^*_f\). ▨

Next recall the reduced cost optimality condition from Lemma 6.2, which states that a flow \(f\) is a minimum-cost flow if and only if there exists a potential function \(\pi\) that satisfies \(c^\pi_e \ge 0\) for every edge \(e \in G^f\). Just as the definition of an \(\epsilon\)-optimal flow above is a relaxation of the complementary slackness characterization of a minimum-cost flow in Lemma 6.1, the following lemma can be seen as a relaxation of Lemma 6.2. It shows that a flow is \(\epsilon\)-optimal if and only if there exists a potential function \(\pi\) such that \(c^\pi_e \ge -\epsilon\) for every edge \(e \in G^f\).

Lemma 6.35: Every tight potential function \(\pi\) for a flow \(f\) satisfies \(c^\pi_{x,y} \ge \mu^*_f\) for every edge \((x, y) \in G^f\) and \(c^\pi_{x,y} = \mu^*_f\) for every edge \((x, y)\) in a minimum mean cost cycle in \(G^f\).

Proof: The proof of Lemma 6.34 shows that \(c^\pi_{x,y} \ge -\epsilon_f = \mu^*_f\) for every edge \((x, y) \in G^f\).

Next consider any minimum mean cost cycle \(C\). Its cost is \(\mu^*_f|C| = \sum_{(x, y) \in C} c^f_{x,y} = \sum_{(x, y) \in C} c^\pi_{x,y}\). Since \(c^\pi_{x,y} \ge \mu^*_f\) for all \((x, y) \in C\), this implies that \(c^\pi_{x,y} = \mu^*_f\) for all \((x, y) \in C\). ▨

Using Lemmas 6.34 and 6.35, we can now complete the first part of the analysis: We show that the sequence of flows \(f^{(0)}, \ldots, f^{(t)}\) produced by the algorithm satisfies

\[\epsilon_{f^{(0)}} \ge \cdots \ge \epsilon_{f^{(t)}}.\]

Lemma 6.36: \(\epsilon_{f^{(i)}} \le \epsilon_{f^{(i-1)}}\) for all \(1 \le i \le t\).

Proof: Let \(C^{(i-1)}\) be the minimum mean cost cycle in \(G^{f^{(i-1)}}\) that is cancelled to obtain \(f^{(i)}\) and let \(\pi\) be a tight potential function for \(f^{(i-1)}\).

For any edge \((x, y) \in G^{f^{(i)}}\), if \((x, y) \in G^{f^{(i-1)}}\), then \(c^\pi_{x,y} \ge \mu^*_{f^{(i-1)}}\), by Lemma 6.35.

If \((x, y) \notin G^{f^{(i-1)}}\), then \((y, x) \in C^{(i-1)}\) because only the reversals of edges in \(C^{(i-1)}\) can be introduced into \(G^{f^{(i)}}\). Therefore, by Lemma 6.35 again, \(c^\pi_{y,x} = \mu^*_{f^{(i)}}\) and \(c^\pi_{x,y} = -c^\pi_{y,x} = -\mu^*_{f^{(i)}}\). Since \(f^{(i-1)}\) is not the final flow produced by the algorithm, it satisfies \(\mu^*_{f^{(i-1)}} < 0\), so \(c^\pi_{x,y} > 0 > \mu^*_{f^{(i-1)}}\).

This shows that every edge \((x, y)\) in \(G^{f^{(i)}}\) satisfies \(c^\pi_{x,y} \ge \mu^*_{f^{(i-1)}}\), which implies that every cycle in \(G^{f^{(i)}}\) has mean cost at least \(\mu^*_{f^{(i-1)}}\), that is, \(\mu^*_{f^{(i)}} \ge \mu^*_{f^{(i-1)}}\). Thus, by Lemma 6.34, \(\epsilon_{f^{(i)}} \le \epsilon_{f^{(i-1)}}\). ▨

Lemma 6.36 is reassuring but does not guarantee that the algorithm ever produces a \(0\)-optimal flow, that is, a minimum-cost flow. The next lemma provides the second part of the analysis of the minimum mean cycle cancelling algorithm: It shows that after every \(m\) cycle cancellations, the optimality of the flow improves by a factor of at least \(1 - \frac{1}{n}\).

Lemma 6.37: For all \(0 \le i \le t - m\), \(\epsilon_{f^{(i+m)}} \le \bigl(1-\frac{1}{n}\bigr)\epsilon_{f^{(i)}}\).

Proof: Let \(\pi\) be a tight potential function for the flow \(f^{(i)}\) and consider the sequence \(C^{(i)}, \ldots, C^{(i+m-1)}\) of negative cycles cancelled by the algorithm in the residual networks \(G^{f^{(i)}}, \ldots, G^{f^{(i+m-1)}}\). We call such a cycle \(C^{(j)}\) strongly negative if all its edges have a negative reduced cost \(c^\pi_{x,y}\). Otherwise, it is weakly negative.

First observe that there must exist an index \(i \le j < i + m\) such that \(C^{(j)}\) is weakly negative. Assume the contrary. Then the cycles \(C^{(i)}, \ldots, C^{(i+m-2)}\) are strongly negative. The cancellation of any such cycle \(C^{(j)}\) in \(G^{f^{(j)}}\) produces a residual network \(G^{f^{(j+1)}}\) such that at least one edge \((u, v) \in C^{(j)}\) is not in \(G^{f^{(j+1)}}\). The only edges in \(G^{f^{(j+1)}}\) that are not in \(G^{f^{(j)}}\) are the reversals of the edges in \(C^{(j)}\). Since every edge in \(C^{(j)}\) has a negative reduced cost, all these new edges have positive reduced costs. This shows that \(G^{f^{(j+1)}}\) has strictly fewer edges with negative reduced cost than \(G^{f^{(j)}}\). Since there are at most \(m\) edges with negative reduced cost in \(G^{f^{(i)}}\), this implies that \(G^{f^{(i+m-1)}}\) has at most one edge with negative reduced cost. Since \(C^{(i+m-1)}\) contains at least two edges, at least one of its edges must therefore have non-negative reduced cost, that is, \(C^{(i+m-1)}\) is weakly negative, a contradiction.

So consider the first index \(i \le j < i+m\) such that \(C^{(j)}\) is weakly negative. Then \(\epsilon_{f^{(i+m)}} \le \epsilon_{f^{(j)}}\), by Lemma 6.36. Thus, it suffices to show that \(\epsilon_{f^{(j)}} \le \bigl(1 - \frac{1}{n}\bigr)\epsilon_{f^{(i)}}\). Since all cycles \(C^{(i)}, \ldots, C^{(j-1)}\) are strongly negative, all edges in \(G^{f^{(j)}}\) that are not in \(G^{f^{(i)}}\) have positive reduced cost. Since \(\pi\) is a tight potential function for \(f^{(i)}\), all edges in \(G^{f^{(i)}}\) have a reduced cost no less than \(\mu^*_{f^{(i)}}\), by Lemma 6.35. Thus, every edge \(e \in C^{(j)}\) has reduced cost \(c^\pi_e \ge \mu^*_{f^{(i)}}\) and at least one edge in \(C^{(j)}\) has non-negative reduced cost because \(C^{(j)}\) is weakly negative. Thus, the mean cost of \(C^{(j)}\) is

\[\begin{multline} \mu_{C^{(j)}} = \frac{c^{f^{(j)}}_{C^{(j)}}}{|C^{(j)}|} = \frac{c^\pi_{C^{(j)}}}{|C^{(j)}|} \ge \frac{(|C^{(j)}| - 1)\mu^*_{f^{(i)}}}{|C^{(j)}|} =\\ \left(1 - \frac{1}{|C^{(j)}|}\right)\mu^*_{f^{(i)}} \ge \left(1 - \frac{1}{n}\right)\mu^*_{f^{(i)}} \end{multline}\]

because \(|C^{(j)}| \le n\) and \(\mu^*_{f^{(i)}} < 0\). Since \(C^{(j)}\) is a minimum mean cost cycle in \(G^{f^{(j)}}\), we have \(\mu^*_{f^{(j)}} = \mu_{C^{(j)}}\) and, thus, \(\mu^*_{f^{(j)}} \ge \bigl(1 - \frac{1}{n}\bigr)\mu^*_{f^{(i)}}\). Since \(\epsilon_f = -\mu^*_f\) for every flow \(f\), by Lemma 6.34, this shows that \(\epsilon_{f^{(j)}} \le \bigl(1 - \frac{1}{n}\bigr)\epsilon_{f^{(i)}}\) and, thus, that \(\epsilon_{f^{(i+m)}} \le \bigl(1 - \frac{1}{n}\bigr)\epsilon_{f^{(i)}}\). ▨