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 Problem Set 4 Lecturer: Michel X. Goemans 1. In class, we have seen Klein's cycle cancelling algorithm for the Min Cost Circulation Problem (MCCP). This algorithm requires O(mCU) iterations in the worst case, i.e., its running time is not polynomial in m, log C and log U. In this problem, we will see how to apply the idea of cost scaling on this algorithm to obtain an algorithm whose running time is polynomial in m, log C, and U. (In fact, it is possible to apply the same idea on both costs and capacities to obtain an algorithm whose running time is polynomial in m, log U and log C, but this is not required in this problem.) Recall that in MCCP, a bidirected graph G = (V,E),an anti-symmetric cost function c : E HZ,and a capacity function u :E I+ Zare given. Let n and m denote the num- ber of vertices and edges in G, U = max(v,w)EE W) I, and C = Ic(v,Iu(v, max(v,w)EE w)I. (a) For every integer i, define the cost function di): E HZas follows: cci)(v, w) :=sgn(c(v, w)) 1Ic(y)I] , where sgn(x) is the sign of x. Notice that by the above definition, c(O) (v, w) = c(v, w) and C(~'O~(~+~)~)(V,W) = 0. Our objective is to find a way to solve MCCP for the cost function di),given its solution for c(~+'). Let f be an optimum circulation for G with the cost function c(~+')and the capacity function u. Prove that if we apply Klein's cycle cancelling algorithm on G with the cost function c(~)and capacity function u, starting from the circulation f, then the number of iterations of this algorithm is O(mU) . (b) Use part (a) to obtain an algorithm for MCCP that requires O(mU log C) iter- at ions. 2. Consider a directed graph G = (V,E) with a length function 1 :E +Zand a specified source vertex s E V. The Bellman-Ford shortest path algorithm computes the shortest path lengths d(v) between s and every vertex v E V, assuming that G has no directed cycle of negative length (otherwise the problem is NP-hard). Here is a description of this algorithm: The Bellman-Ford algorithm computes d(v) by computing dk (v) = the shortest walk1 between s and v using exactly k edges. dk(v) can be computed by the recurrence dk(v)= min [dk-1(w) +l(w,v)]. (w,v)EE 'A walk is like a path except that vertices might be repeated.Let hl(v) = min dk(v). It can be shown that if the graph has no negative cycle then k=l,...,1 hnPl (v) =d(v) 'for all v E V. Moreover, the graph has no negative cycle iff, for all v, dn(u) 2hn-l(u)-(You are not required to prove any of the above facts.) (a) Let p* be the minimum average length of a directed cycle C of G, i.e., p*(G) = min p(C) =min C(U,V)Ec ~ ( u Y 21) directed cycles c c ICI Using the Bellman-Ford algorithm, show how to compute p* in O(nm) time. (Hint: Use the fact that if we decrease the length of each edge by p the average length of any cycle decreases by p.) (b) Can you find the cycle C with p(C) =p* using only 0(n2)additional time? (In other words, suppose you are given all the values that the Bellman-Ford algorithm computes. Can you find a minimum mean cost cycle using this information in 0(n2)?) 3. Suppose we have n objects that we want to store in a data structure. After storing these objects in the data structure, we would like to perform m find operations on the data structure. Assume that the i'th object is accessed ki21 times. Therefore, Cr=l =m. We want to evaluate the performance of the data structure by comput- ing the total running time of these m find queries (no other operation, such as delete or insert, is performed on the data structure). (a) Show that if we store the objects in a splay tree, then no matter what the initial configuration of the splay tree is, and no matter in which order we access the objects, the total running time of the m access operations is at most (b) Show that if we store the objects in a static binary search tree (i.e., a binary search tree that does not change by a find operation), then no matter in which order the objects are stored in the BST, and no matter in which order they are accessed, the total running time of the m access operations is at least This shows that the splay trees are within a constant factor as optimal as any static binary search