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 October 24, 2001 Lecture 12 Lecturer: Michel X. Goemans Scribe: David Woodruff and Xzaowen Xin In this lecture we continue the presentation of the Cancel and Tighten Algorithm for solving the mini- mum cost circulation problem. In our initial analysis, we will determine the algorithm's running time to be O(min(nn2 log(&), m2n log(2n))). The latter half of today's lecture will be devoted to splay trees, a data structure which will help reduce this running time to O(min(nn log(nC) log n, m2n log2 n)). 1 Cancel and Tighten 1.1 The Algorithm Definition 1 The admissible edges of a residual network Gp are defined to be the set of edges {(v, w) E Ef :cp(v, W) < 0). An admissible cycle of the residual graph Gf is a cycle consisting solely of admissible edges. The admissible graph is the subgraph of G consisting solely of the admissible edges of Ef . Cancel and Tighten Algorithm: 1. Initialize f ,p, E. 2. While f is not optimum, i.e., G contains a negative cost cycle, do: (a) Cancel: While Gp contains an admissible cycle r, push as much flow as possible along r. (b) Tighten: Find p', E', such that f is E'-optimum with respect to p' and E' 5 (1-lln)~. At any point in the algorithm we will have a circulation f, a potential function p, and an E such that f is E-optimum with respect to p. Recall that f is said to be E-optimum with respect to p if V(v, W) E Ef,cp(v, W) 2 -E. TO initialize the algorithm, we will assume that f = 0 satisfies the capacity constraints (i-e., f = 0 is a circulation). If this is not the case, then a circulation can be obtained by solving one maximum flow problem or by modifying the instance so that a circulation can easily be found. Our initial potential function p will be the zero function. Setting E = max Ic(v, w)l, (v,w) EE we surely have that f is E-optimal, i.e., that The existence of p', E', in the tighten step follows from a lemma shown last time or from Theorem 10 in the notes. 1.2 Analysis Each time we complete a tighten step, we reduce e by a factor of 1-lln. Starting with E=C= max Ic(v,w)I, (v,w)€Ea simple argument given last time shows that c will be less than l/n after O(nlog(nC)) tighten steps, which will then imply that f is optimal. Alternatively, after n log(2n) iterations of tighten, one additional edge is €-fixed, and that edge remains fixed because ~(f) does not increase as the algorithm progresses. Using this alternative analysis, we obtain the strongly polynomial bound of O(mnlog(2n)) iterations of the tighten step. To determine the overall running time of the Cancel and Tighten Algorithm we need to determine the time spent for each cancel step and for each tighten step. Implementing the Tighten Step: To implement the tighten step, we could use an extended Bellman-Ford algorithm to find the minimum mean cost cycle in O(mn) time. This would be sufficient for our purposes, but is not necessary. We need only find a p', el, such that f is E'-optimum with respect to p1 and E' < (1-l/n)e. After the cancel step completes, we know there are no cycles in the admissible graph. Therefore we can take a topological ordering of the admissible graph to rank the vertices so that for every edge (u, w) in the admissible graph, rank(u) < rank(w). This ranking of the vertices can be done in O(m) time using a standard topological sort algorithm. Letting l(u) : V + {0,1,2,...,n -1) denote the rank function on the vertices V of Gf,we have 1(w) > 1(v)if (u, w) is an admissible edge of Ef. For each vertex v of V, we define our new potential function p' by p' (u) =p(u) -1 (u) cln. Claim 1 p' is such that f is 8-optimal with respect to p', where E' < (1-lln)~. Proof of claim 1: Suppose (u, w) E Ef.Then, Casel: (v, w) was admissible: cb(v, w) = cp(u, w) + c/n(l (w) -l(v)) > -e+c/n > -(I- l/n)c Case2: (v, w) was not admissible: cb(v, w) = cp(u, w) + c/n(l (w) -1(u)) > 0 -c/n(n-1) = -(1 -l/n)c Hence, in either case, f is €'-optimal with respect to p', where E' < (1-l/n)c. Implementing the Cancel Step: We now shift our focus to the implementation of the cancel step. The goal in the cancel step is to saturate at least one edge in every cycle in the admissible graph G = (V,A). We will implement this with a Depth-First-Search (DFS), pushing flow to saturate and remove edges every time we encounter a cycle, and removing edges whenever we determine that they cannot be part of any cycle. The algorithm is:Cancel Step algorithm(G = (V, A)) : 1. Choose v in V. Begin a DFS rooted at v. (a) If we encounter a vertex w that we have previously encountered on our path from v, we have found a cycle r. In this case, we let S = min(,,w),r u(v, w). We then increase the flow along each of the edges of by S, saturating at least one edge. We remove the saturated edges from A, and recurse with G1= (V, A'), where A' denotes the edges of A with the saturated edges removed. (b) If we encounter a vertex w such that there are no edges emanating from w in G, we backtrack until we find an ancestor r of w for which there is another child to explore. As we backtrack, we remove the edges we backtrack along from A until we encounter r. We continue the DFS by exploring paths emanating at r. Every edge e f A that is not part of any cycle is visited at most two times, and hence the running time to remove edges that are not part of any cycle is O(m). For each cycle that we cancel, we need to determine u = min u(v,w) ('u,'w)Er and update the flow along each of the edges of the cycle. Since there can be at most n -1edges in a cycle, we spend O(n) time per cycle cancelled. Since we saturate and remove at least one edge from A every time we cancel a cycle, we can cancel at most m cycles. Hence, the overall running time of the cancel step is 0(m +nm) = 0(mn). Overall Running Time: Note that the cancel step requires O(mn) time per iteration, whereas the tighten step only requires O(m) time. Hence, the cancel step is the bottleneck of the Can- cel and Tighten Algorithm. Earlier we determined that the number of iterations of the Can- cel and Tighten Algorithm is O(min(n log(nC), mn log(2n))). Hence the overall running time