MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms September 15, 2008 Goldberg-Tarjan Min-Cost Circulation Algorithm Lecturer: Michel X. Goemans 1 Introduction In this lecture we shall study Klein’s cycle cancelling algorithm for finding the circulation of minimum cost in greater detail. We will pay particular attention to the choice of cycle to cancel and we will rigorously prove two bounds on the number of iterations required, the first of which depends on the magnitude of the cost and is valid only for integer-valued costs, and the second of which is strongly polynomial and works even for irrational costs. Recall from last time that for a given circulation f, the following are equivalent: i. f is of minimum cost ii. There is no negative cost cycle in the residual graph Gf iii. There exist potentials p : V � R such that the reduced costs cp(v, w) = c(v, w) + p(v) − p(w) � 0 for all (v, w) ≥ Ef , where Ef = {e : uf (e) > 0}. 2 Klein’s cycle cancelling algorithm Algorithm 1 Kleins-Cycle-Cancel(Gf ) Let f be any circulation (e.g., f = 0) while there exists a negative cost cycle � ≥ Gf do Push �(f) = min uf (v, w) along � (v,w)�� end while It is important to note that the Ford-Fulkerson algorithm for the maximum flow problem is a special case of Klein’s cycle cancelling algorithm, by defining zero costs for all edges in the original graph and by adding an extra edge from the sink to the source with cost −1. 2.1 Choice of cycle � As in the Ford-Fulkerson algorithm, the question is which negative-cost cycle to choose. 1. (Weintraub 1972). One idea is to try choosing the maximum improvement cycle, where the difference in cost is as large as possible. One can show that the number of iterations is polynomial for rational costs, but finding such a cycle is NP-hard. For irrational costs, one can show that this algorithm may never terminate (Queyranne 1980) even for the maximum flow problem (the fattest augmenting path algorithm of Edmonds and Karp), although the solution converges to a minimum cost flow. lect-1�|�| |�| 2. (Goldberg-Tarjan 1986). Alternatively, we can choose the cycle of minimum mean cost, defined as follows: µ(f) = min directed cycles � ≥ Gf c(�) |�| � where c(�) = (v,w)�� c(v, w) and |�| is the number of edges in the cycle. Notice that there exists a negative cost cycle in Gf if and only if µ(f) is negative. To see that we can indeed find the minimum mean-cost cycle efficiently, suppose we replace the costs c with c� such that c�(v, w) = c(v, w) + � for each edge (v, w). Then µ�(f) = µ(f) + �, so if � = −µ(f ) then we would have µ�(f) = 0. In particular, µ(f) = − inf{� : there is no negative cost cycle in Gf with respect to costs c + �}. For any �, we can decide if there is a negative cost cycle by using the Bellman-Ford algorithm. Now, perform binary search to find the smallest � for which no such cycle exists. In the next problem set we will show a result by Karp, which finds the cycle of minimum mean cost in O(nm) time by using a variant of Bellman-Ford. 2.2 Bounding the number of iterations We will give two bounds on the number of iterations for the algorithm. The first depends on the magnitude of the cost and is valid only for integer-valued costs; it is polynomial but not strongly polynomial. The second bound is strongly polynomial and works even for irrational costs. We first need a measure of ‘closeness’ to the optimal circulation. The following definition gives such a measure, and will be key in quantifying the progress of the algorithm. Definition 1 (Relaxed optimality) A circulation f is said to be �-optimal if there exists a po-tential p : V � R such that cp(v, w) � −� for all edges (v, w) ≥ Ef . Note that an 0-optimal circulation is of minimum cost. Definition 2 For a circulation f, let �(f) = min{� : f is �-optimal}. One important thing about this that we will prove soon is that when we push some flow in a circulation f along some cycle � and obtain a new circulation f �, we get that �(f �) � �(f ). This means that � is monotonically non-increasing in general. First, we need the following strong relationship between �(f) and µ(f ), and this really justifies the choice of cycle of Goldberg and Tarjan. Theorem 1 For all circulations f, �(f ) = −µ(f). Proof: We first show that µ(f ) � −�(f). From the definition of �(f ) there exists a potential p : V � R such that cp(v, w) � −�(f ) for all (v, w) ≥ Ef . For any cycle � ≤ Ef the cost c(�) is equal to the reduced cost cp(�) since the potentials cancel. Therefore c(�) = cp(�) � −|�|�(f) and c(�)so |�| � −�(f ) for all cycles �. Hence µ(f) � −�(f). Next, we show that µ(f) � −�(f). For this, we start with the definition of µ(f ). For every c(�)cycle � ≥ Ef it holds that |�| � µ(f ). Let c�(v, w) = c(v, w) − µ(f ) for all (v, w) ≥ Ef . Then, c (�) c(�)= − µ(f) � 0 for any cycle �. Now define p(v) as the cost of the shortest path from an added source s to v with respect to c� in Gf (see Fig. 1); the reason we add a vertex s is to make sure that every vertex can be reached (by the direct path). Note that the shortest paths are well-defined since there are no negative cost cycles with respect to c� . By the optimality property of shortest lect-2c’(v,w)s 0 0 0 v w Figure 1: p(v) is the length of the shortest path from s to v. paths, p(w) � p(v) + c�(v, w) = p(v) + c(v, w) − µ(f). Therefore cp(v, w) � µ(f) for all (v, w) ≥ Ef which implies that f is −µ(f)-optimal and thus �(f) � −µ(f ). By combining µ(f) � −�(f) and �(f ) � −µ(f) we conclude �(f) = −µ(f ) as required. � The nature of the algorithm is to push flow along negative cost cycles. We would like to know if this actually gets us closer to optimality. This is shown in the following remark. Remark 1 (Progress) Let f be a circulation. If we push flow along the minimum mean cost cycle � in Gf and obtain circulation f � then �(f ) � �(f �). cp(�) c(�)Proof: By