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 3 If you have any doubt about the collaboration policy, please check the course webpage. Problem 1. Consider the symmetric traveling salesman path problem. We are given a set V of vertices, a (symmetric) distance d(i, j) = d(j, i) ≥ 0 for every pair i, j of vertices, 2 special vertices s and t, and we would like to find a path from s to t passing through all vertices (a Hamiltonian path) and of minimum total length. This problem is NP-hard, and so we will not try to solve it exactly in polynomial time. One simple heuristic is known as 2-OPT. Start from any ordering v1 = s, v2, , vn = · · · t and remove 2 non-consecutive edges of the Hamiltonian path, say (vi, vi+1) and (vj , vj+1) where i +1 < j. Now, there is a unique way to form a new Hamilonian path by adding 2 other edges, namely (vi, vj ) and (vi+1, vj+1). If this results in a path of shorter length, this so-called 2-swap is performed, and this is repeated until no more improvements are possible. Now suppose we would like to create a data structure to maintain the ordering of the vertices on the path. For any vertex v, we would like to be able to find Next(v), the vertex following v on the way to it, and similarly Previous(v), the vertex preceding v (i.e. closer to s). The tricky thing is that when we perform a 2-swap, the vertices vi+1 to vj are now visited in the reverse order (from vi we go to vj , then to vj−1 and continue all the way to vi+1, and then continue at vj+1). This means we would also like to have an operation Reverse(v, w) that reverses the ordering from v to w; in our case above we would perform Reverse(vi+1, vj ). If we were maintaining the ordering as a doubly-linked list (with pointers next and previous), a Reverse operation would require Θ(n) time in the worst-case. Show how to use splay trees to maintain the ordering and perform any sequence of m operations (Next, Previous, or Reverse) in O((m + n) log n) time. (If you augment the splay tree with additional information at every node, you must indicate how this information is maintained while performing operations.) Problem 2. In lecture, we argued the static optimality property of splay trees by showing that the time T required for a splay tree to access element i mi ≥ 1 times for i = 1, , n is within a constant of the time required by any static BST. In this · · · problem, you need to argue that this time T for splay trees is � m O mi 1 + log , mii PS3-1� where m = i mi is the total number of accesses. Problem 3. In the blocking flow problem (which arises in the blocking flow al-gorithm for the maximum flow problem), we are given a directed acyclic graph G = (V, E), 2 vertices s and t and capacities on the edges. The goal is to find a flow f such that for every path P in E from s to t at least one of the edges of P is saturated (i.e. f(v, w) = u(v, w)). 1. Is the following argument correct? A blocking flow f is maximum since, if we take S to be the set of vertices reachable from s in (V, E) by non-saturated edges, we get ¯a cut (S : S) whose value equals the blocking flow, and hence the blocking flow must be optimal. If the argument is fallacious, show a blocking flow which is not maximum. 2. Show how to find a blocking flow in a graph G = (V, E) with n vertices and m edges in O(m log n) time. (Your solution can be quite short.) (FYI, Dinitz showed that one can solve a maximum flow problem in a general directed graph by solving at most n blocking flow problems in directed acyclic graphs.) Problem 4. A team of n members would like to travel a distance d from A to B as quickly as possible. All of them can walk and have also one scooter (which can carry only one person at a time) that they can use. For each person i (1 ≤ i ≤ n), we know his/her walking speed wi and his/her s peed si when travelling on the scooter. The goal is to find a way to bring all n people to destination so as to minimize the time at which the last person arrives. The scooter can b e left by any member of the group on the side of the road, and picked up by anyone else of the group. Members of the group can also walk or use the scooter backwards (towards A) if that helps. 1. Consider the case where n = 3, w1 = w2 = 1, s1 = s2 = 6, w3 = 2, s3 = 8 and d = 100. Find the fastest way for everyone to travel the distance d. 2. For a general instance (general n and arbitrary speeds), write a linear program whose value is always a lower bound on the time neede d for the n-person team to travel a distance d. This should be a small linear program; the number of variables and constraints should be O(n) (and not dependent on d, or the number of ’legs’ of the solution). 3. Use the linear programming routines in matlab (or any LP software like CPLEX) to compute your lower bound for the instance given in 1. (You don’t have to use a linear programming software, provided you can exhibit an optimum solution, with a proof of optimality.) PS3-2� � If the bound you obtain is not equal to the value you found in 1., either improve your solution to 1., or find a stronger linear program in 2. Matlab is available on athena, see http://web.mit.edu/olh/Matlab/Matlab.html for more info. Type help linprog for information on how to use the LP rou-tine. Problem 5 . We will rederive the max-flow min-cut theorem from linear program-ming duality. Consider the maximum flow problem on a directed graph G = (V, E) with source s ∈ V , sink t ∈ V and edge capacities u : E → R. The max-flow problem is a linear program: max w subject to ⎧ � � ⎨ w i = s xij − xji = ⎩ 0 i =� s, t j j −w i = t xi,j ≤ ui,j (i, j) ∈ E 0 ≤ xi,j (i, j) ∈ E. The variables are the xij ’s (one per edge) and w. 1. Show that its dual is equivalent to: min uijyij (i,j)∈E subject to zi − zj + yij ≥ 0 (i, j) ∈ E zs = 0, zt = 1 yij ≥ 0 (i, j) ∈ E. 2. Given a cut (S : S) …