DOC PREVIEW
MIT 6 854 - Minimum Cost Circulation Problem

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 Lecture 10 Lecturer: Michel X. Goemans October 17, 2001 Scribe: Ashish Koul 1 Minimum Cost Circulation Problem Theorem 1 Let f be a circulation. The following are equivalent: (i) f is of minimum cost. (ii) Gfhas no negative cost directed cycles. (iii) 3p : cp(u,w) 20 V(u, w) E Ef, where cp(v,w) = c(u,w) +p(u) -p(w). Proof: i j ii and iii +-i were proven last lecture. All that remains is the proof of ii +-iii: Let G' be obtained from the residual graph Gfby adding a vertex s linked to all other vertices by edges of cost 0 (the costs of these edges do not matter). Let p(u) be the length of the shortest path from s to v in G'with respect to the costs. These quantities are well-defined since Gf does not contain any negative cost directed cycles, and every vertex is reachable from s. By definition of the shortest paths, p(w) 5 p(u) +c(u,w) V(u,w) E Ef. This implies that cp(u,w) > 0 V(u,w) E Ef. 2 Klein's Algorithm for MCCP Klein's Cycle canceling algorithm: 1. Let f be any circulation. 2. While Gf contains a negative cycle r do push 6 = min(,,,)Er vf (u,w) along I?. Argument for Correctness: If the algorithm terminates, then the circulation found must be optimum. Furthermore, if all ca-pacities and costs are integers, then the algorithm will terminate. Why? f (v, w) is always an integer, thus 6 =min(,,,)Er uf(u,w) 21 If Ic(u,w)I 5 C and If (u,w)1 5 U, then the absolute value of the cost of the optimal circulation is at most mCU Therefore, the algorithm terminates after 0(mCU) iterations. Remark 1 If the edge capacities in the graph are irrational, then the algorithm is not correct. The cycle canceling algorithm can be applied to the Max-Flow Problem by making appropriate modifications to the graph G. Let G' be obtained by setting the cost of all edges within G to 0. Furthermore, select two vertices s and t from within the graph, and add the directed edges (s,t) and (t,s), where c(s,t) = 1,c(t, s) = -1 and both edges have infinite capacity. Now, solving forthe maximum flow between s to t is equivalent to solving for the minimum cost circulation, which contains s and t. In this circumstance, Klein's Algorithm reduces to the Ford-Fulkerson Algorithm. Ford-Fulkerson Augmenting Path Algorithm: 1. Begin with zero flow: f = 0. 2. While Gf contains a directed path P from s to t do push 6 = min(,,,),p u (v,w) along P. The running time given above for Klein's Cycle-Canceling Algorithm is not polynomial. The nega- tive cost cycle in Klein's Algorithm (or the directed path in the Ford-Fulkerson Algorithm) must be chosen appropriately to insure a polynomial running time. Candidates for Cycles in Klein's Algorithm: 1. The most negative cost cycle in Gf ? Finding this cycle is an NP-Hard problem, so it would not be a viable choice. 2. The negative cycle in Gf which would yield the maximum cost improvement? Finding this cycle is again an NP-Hard problem. However for the Max-Flow Problem, this choice reduces to finding the st-path with maximum residual capacity. Such a path can be found in O(m) time, m = IEl. The resulting Max- Flow algorithm is known as the '<fattestv path algorithm (Edmonds-Karp '72). The number of iterations necessary is O(m log U), thus the running of the algorithm is O(m2 log U). 3. Minimum Mean-Cost Cycle? Define the mean cost of a cycle r to be: where Irl denotes the number of edges in r. The minimum mean cost of all cycles of the residual graph Gf would thus be: min -c(r) '(') = cycles T. in G~ lr1 The minimum mean-cost cycle can be determined in strongly polynomial time by using a modified version of the Bellman-Ford Algorithm. More precisely, the minimum mean cost cycle can be found in O(mn) time. Using this method to solve the Min-Cost Circulation Problem yields the Goldberg-Tarjan Algorithm, which runs in polynomial time. Using this method to solve the Max-Flow Problem yields what is known as the "shortest" augmenting path algorithm (Edmonds-Karp) . This Max-Flow Algorithm is able to find the augmenting path in O(m) time, and requires O(mn) iterations to arrive at the solution. Thus, the total running time is 0(m2 n) .3 The Goldberg-Tarjan Algorithm Goldberg-Tarjan Algorithm: 1. Begin with zero flow: f =0. 2. While p(f) < 0do push 6 = min(,,,),I- uf (u,w) along a minimum mean cost cycle r of Gf . Analysis of Goldberg-Tarjan Algorithm: In order to analyze this algorithm, it is necessary to define the concept of proximity measure for a circulation f. Definition 1 A circulation f is E-optimalif there exists p such that cp(u,w) 2-E V(u,W)E Ef. Definition 2 ~(f)= minimum E such that f is E-optimal. The following theorem states that the minimum mean cost p(f) of all cycles in Gf is equal to -E( f), as defined above. Theorem 2 For any circulation f, p(f) = -E( f). Proof: ~(f)2-4f) By definition, there exists p such that cp(u,w) > -E( f) V(v,w) E Ef . Thus, it is implied that cP(r) 2 -~(f)lI'l for any directed cycle r E Gf. But for any I' E Gf, c(r) = cp(r). Thus, dividing both sides by Irl yields that the mean cost of any directed cycle I'E Gf is at least -~(f).Therefore, p(f) 2-~(f). 461 I-4f 1 Consider p(f). For every cycle r E Gf, it is the case that > p(f). Let cl(v,w) = C(U, W)-p(f) V(u,W) E Ef. With respect to this new cost function c' every cycle I'E Gf will have nonnegative cost. Now, let G' be obtained by adding a new node s to Gf and adding directed edges from s to u Vu E V, all with zero cost. Let p(u) be the cost with respect to c' of the shortest path from s to u in the new graph G'. For all edges (u,w), p(w) Ip(u)+c'(u,w) =p(u)+c(u,w)-p(f). This implies that cp(v,w) > p(f) V(u,w) E Ef. Therefore, ~(f)5 -p(f). Remark 2 Along the minimum mean cost cycle I', cp(v,w) = -E(f) V(v,w) E I'. Having completed the necessary definitions and proofs, we may now proceed with the analysis of the Goldberg-Tarjan Algorithm. The following theorem considers only one iteration of the algorithm. Theorem 3 Let f be a circulation and let f' be the circulation obtained by canceling the minimum mean cost cycle I'of Gf . Then, E(f') < E(f). Proof: By definition, there existspsuch that cp(u,w) > -~(f)V(u,w) E Ef. In the caseof


View Full Document

MIT 6 854 - Minimum Cost Circulation Problem

Download Minimum Cost Circulation Problem
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Minimum Cost Circulation Problem and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Minimum Cost Circulation Problem 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?