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 2 If you have any doubt about the collaboration policy, please check the course webpage. Problems: 1. Given a directed graph G = (V, E), a source s ∈ V , a sink t ∈ V and a length function l : E → R, the fattest path problem is to find a simple path P from s to t which maximizes min(v,w)∈P l(v, w). (a) Give a modification of Dijkstra’s algorithm for the shortest path problem which solves the fattest path problem. Argue correctness of your algorithm. (b) Suppose that all arcs lengths are integer-valued between 1 and m where m = | E|. Can you provide an implementation o f your algorithm that runs in O(m) time? (Hint: Do not use any fancy priority queue.) 2. In this problem, you will show that the fattest augmenting path algorithm for the maximum flow problem can be implemented to run in O(m) time per itera-tion after some basic preprocessing. Remember that in the fattest augmenting path algorithm, the augmenting path with largest minimum residual capacity is chosen at every iteration. (a) Show that if we have a total ordering of the residual capacities then the fattest augmenting path can be found in O(m) time. (b) Show that , this total o r dering of the residual capacities can be maintained in O(m) time aft er pushing flow along one augmenting path (how do the residual capacities change)? (c) What is the running time ofthe resulting inplement ation of the fattest augmenting path algorithm? 3. Consider a directed graph G = (V, E) with a length function l : E → Z and a specified source vertex s ∈ V . The Bellman-Ford shortest path a lg orithm computes the shortest path lengths d(v) between s and every vertex v ∈ V , assuming that G has no directed cycle of negative length (otherwise the problem is NP-har d). 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 1A walk is like a path except that vertices might be repeated. PS2-1�recurrence dk(v) = min [dk−1(w) + l(w, v)] . (w,v)∈E Let hl(v) = min dk(v). It can b e shown that if the graph has no negative cycle k=1,...,l then hn−1(v) = d(v) for all v ∈ V . Moreover, the graph has no negative cycle iff, for all v, dn(v) ≥ hn−1(v). (You are not required to prove any of the above facts.) (a) Let µ ∗ be the minimum average length of a directed cycle C of G, i.e., l(u, v) µ ∗(G) = min µ(C) = min (u,v)∈C . directed cycles CC |C| Using the Bellman-Ford algorithm, show how t o compute µ ∗ in O(nm) time. (Hint: Use the fact that if we decrease the length of each edge by µ the average length of any cycle decreases by µ.) ∗(b) Can you find t he cycle C with µ(C) = µ using only O(n2) additional time? (In other words, suppose you are given all the values that the Bellman-Ford algorithm computes. Can yo u find a minimum mean cost cycle using this information in O(n2)?) 4. In this problem, we will prop ose anot her way to solve the minimum mean cost cycle problem. The resulting algor ithm will be quite slow, but the technique is widely applicable (and for other problems, this will give the fastest known approach). The problem of finding µ ∗ is equivalent to the problem of finding the largest value of µ such that the graph with lengths lµ(u, v) = l(u, v) − µ has no negative cycles. (a) Argue that for a given value of µ, we can decide whether µ ∗ ≥ µ or µ ∗ < µ by performing at most O(A(m, n)) additions of 2 numbers and O(C(m, n)) comparisons involving 2 numbers (and no other operations except control statements). Please state the values you can obtain for A(m, n) and C(m, n). Observe that, as we are performing only additions and comparisons, all the numbers involved are linear f unctions of the input lengths and µ. (b) Now suppose we run the above algorithm with µ equal to the unknown value µ ∗ . We can easily perform the additions provided that we store all the numbers (including the inputs) as linear functions of µ ∗ (i.e. of the form a + bµ∗). Explain how we can resolve the comparisons (even though we do not know µ ∗). (It is normal if the solution requires a fair amount of time to resolve each comparison.) As a function of A(m, n) and C(m, n), what is the total running time of your algorithm to compute µ ∗? PS2-25. We argued in lecture that for the maximum flow problem, there always exists a maximum flow which is integer-valued if the capacities are integral. Prove that a corresponding statement for minimum cost circulations also holds, namely that if the capacities and the costs are integer-va lued then (i) the minimum cost circulation can be chosen to be integer-valued and (ii) the vertex potentials proving optimality can also be chosen to be integer-valued. 6. In this problem, we will add a time dimension to network flows. Suppose we have a network G = (V, E) in which each arc has unit capacity (u(v, w) = 1 for all arcs (v, w)), and we have two special vertices, a source s and a sink t. Our network for example could be a computer network and our unit of flow could be a packet. Each arc also has an integer-valued transit time τ(v, w) ∈ Z+ which represents the time it takes (a unit of flow or packet) to travel through the arc. At every unit of time, say at time d, only one packet can enter the arc (there might be several packets already travelling through the arc since there could have been packets injected in it at times d − 1, d − 2, etc.). We can assume that vertices can instantaneously accept packets on its incoming