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 November 21, 2000 Lecture 18 Lecturer: Michel X. Goemans Scribe: Ahmed Ismail and Johnny Chen In the previous lecture, we discussed the Bar-Yehuda and Even 2-approximation algorithm for the vertex cover problem, and introduced the Generalized Steiner tree problem, and outlined a 2-approximation algorithm of Goemans and Williamson which formulates the problem using duality which constructs both an integer solution and a dual solution of a relaxed version of the problem, and began the construction of the proof of correctness of the algorithm. 1 The Generalized Steiner tree problem Problem 1 (Generalized Steiner tree problem) Given a graph G = (V,E) with costs c (e) 2 0,Qe E E, and a set of vertex pairs T & V x V, find a subgraph F of minimum cost such that Q (s, t) E T, s and t are connected in F. As a linear program, this problem can be formulated as trying to determine the optimal solution OPT for min Cc(e)x (e) , eEE such that where Rather than deal with this complicated integer linear program, Goemans and Williamson relax the problem by replacing the integer constraint (3) with a nonnegativity constraint, and therefore look for the solution LB which satisfies (1) subject to the constraints (2) as well as x (e)2 0,Qe. Goemans and Williamson also consider the corresponding dual problem, such that Considering (1) and (5) together, we can obtain both a feasible set of edges F as well as a set of ys's satisfying (6), such that Cc(e) 5 2 C ys5 20~~. The details of the algorithm to compute F and the ys's were provided in the previous lecture.2 Eliminating the ys's Our aim is to establish that (8) is valid for the Goemans-Williamson algorithm. However, before we resume our proof of its correctness, we note that although we keep track of the ys's for the purpose of establishing correctness, we do not actually use the ys's as variables when implementing this algorithm. Instead, we choose to keep track of d (i), which is defined as d (4 = C Ys, for every vertex i. Then, for an edge (i, j) E 6 (S) , where i and j belong to different connected components of F, The goal of the dual program is to maximize each ys while still obeying the constraints implied by (6);if we choose to ignore the individual ys9s, we can try to minimize c, -d (i) -d (j) instead. Thus, our algorithm proceeds as follows. Initialize [F= 0; C = {{i) : i E V); d(i) t0 Vi E V; k t1;(ys t0 VS E F)]; While FnC # 0 do: (see observation in notes below) cij -d(i) -d (j)c = min ( min min cij -d (i) -d (j)iECP7jECq7~#q,Cp,Cq€F 2 ' iECp7jECq7~#q,Cp€F7Cq#F Let ek t(i,j) attain this minimum. ForC€CnF: For i E C: d(i) td(i) +c; F tF u{ek); ktk+l; Update the connected components C; F' tF; For l tk -1down to 1: if F' -{el) is feasible then F' tF' -{el); (delete step) Output F'. Note that the delete step in the algorithm, as written above, is easier for the purposes of the proof. However, we do not need to perform the delete in this manner: although we can cycle through the edges in the order in which we added them, we can also attempt to remove them in any order. Either route will yield the unique solution which has paths between our pairs of vertices s's and t's, which will be the same result as using the condition F' = {e E F : F \ {e) is not feasible) .3 Correctness of the algorithm Our goal is to establish the following result. Theorem 1 The algorithm of Goemans and Williamson returns a feasible set of edges F and a set of ys 's such that Cc(e) 52C ys 520PT. (9) In our previous lecture, we established the following lemma. Lemma 2 If C nF = 0, then F is feasible. Thus, since by construction the algorithm only terminates if C n F = 0, we know that any resulting F obtained is feasible. We thus focus on establishing the inequality (9). Let us first define two sets 0 and E as follows. Definition 1 ~etO=Cn.FandE=CnF, so thatC=EUO. We now construct a graph H = (C, E (H)) by shrinking all the connected components into vertices. In this construction, the set E (H) is Since H has no cycles, it is a forest, and therefore where dv is the degree of vertex v in the forest H. If H is a single tree, then equality holds. We can ignore all vertices v such that dv = 0. We now want to prove the following result. Lemma 3 There does not exist v E E such that dv = 1. Proof: Suppose that 3v E E : du = 1,where v corresponds to the connected component C, and let el, be the unique edge corresponding to this vertex. Since we could not remove ek during the delete step, there exists an edge (s,t)E T such that s E C, t 4C. However, this implies that which is clearly a contradiction. Thus, there does not exist v E E such that d, = 1. This lemma lets us say that Cancelling like terms from the outside of (10) g'lves us Now, as we know that we can exchange the order of summations to say that Now it remains to prove the following lemma.Lemma 4 During the execution of the algorithm, Proof: The proof of this is carried out by induction on k. The base step is trivial, since we initialize ys =0 at the start of the algorithm. Then, during an iteration, ys increases by an amount e for each S E F nC, so the right-hand side of the inequality increases by 2c IFnCI. By the same reasoning, the left-hand side increases by CstTncc 16(S)nF'I . Thus, we want to show that However, we know by construction that FnC = 0, and when v E 0, 16 (S)nF' I is just the degree du of node v in H. As a result, we have which is a weaker form of the inequality (11). This completes the proof of (12), and with it, of the correctness of the algorithm. I7 4 Implementation and generalizations This approach also works and gives a bound for problems such as for other collections of sets F,F = {S: IS1odd) (for perfect matchings) or F = {S: IS nA1 # IS nBI). With the following implementation considerations, the algorithm runs in 0(n2 1og n) time. The Union-Find data structure can be used to update connected components (in roughly linear time). Instead of using a double loop to find e (which would take m2 time), we can create a "time-axis," keep track of the time when each edge becomes tight, presuming nothing else in the graph changes. Each iteration (there are