DOC PREVIEW
MIT 6 854J - 6 854J Lecture 17

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 19, 2001 Lecture 17 Lecturer: Michel X. Goernans Scribe: Steven Richman, Matt Peters 1 Refresher of Last Lecture We continue our description of approximation algorithms and design. Last lecture we were looking at the problem of Vertex Cover. Vertex Cover (VC): Given undirected graph G =(V,E) and nonegative weights on each vertex w(u) 20 Vv E V, find a vertex cover Sof minimum total weight EVESw (v).A vertex cover satisfies V(u, v) E E{u, u} n Sf0. Last time, we introduced the two-step lower bound technique to analyze approximation algo- rithms. This technique can be generalized to apply to maximization problems, but in this lecture we will restrict our discussion to minimization problems. The first step in the technique is to find a lower bound LB on the optimum solution, and the second step is to show that the analyzed algorithm returns a solution at most axLB. We will use the lower bound technique to analyze our algorithm for Vertex Cover. For this, we will first formulate the vertex cover problem as an integer program (a linear program with integrality constraints). Then we will remove the integrality constraints to obtain a linear program; this is our linear programming relaxation. Since, for this linear program, we are optimizing over a set P' that contains the set P of all integer solutions to our integer program, we obtain a lower bound LB on the optimum vertex cover value. For Vertex Cover, we can describe the optimal solution as min Cw (v)x(v) Using linear relaxation, we get a lower bound: min Cw (u) x(u) We can find a solution to Vertex Cover at most twice this lower bound using the rounding algorithm of Hochbaum (around 1981). This algorithm proceeds by first obtaining the solution x* (v) of the linear program described in (2). A 2-approximation solution to Vertex Cover is then given by (Proof that this is a 2-approximation solution was given in the last lecture.)We now have an algorithm, shown using the lower bound technique to satisfy (i) LB 5 OPT (ii) ~v,sw(v) 5 2LB 1 20PT The drawback of this algorithm is that it requires solving a linear program. Though it is polyno- mial time, it may still be more costly than desired. We will start the new material in this lecture by giving an alternate approach using duality, and again analyze it using the lower bound technique. 2 Bar- Yehuda and Even Vertex Cover 2.1 Duality We take the dual program of the linear program described in (2): LB is equal to the solution of this program by duality. For any y feasible in the dual LP, we have -< LB 5 OPT, and we need only find such a y to have a lower bound on OPT. 2.2 2-Approximation Algorithm (Bar-Yehuda and Even) Algorithm Start with an empty S and with y initialized to 0. Find an edge (u,v) that is not covered, and increase y(u, v) until one of becomes tight. (Since we are increasing y, it will remain nonegative and thus will be feasible.) Add the vertex for which the equation becomes tight to S, and proceed, stopping when S is a vertex cover. y(u,v) t0 V(u,v) E E st0 while S leaves an edge (u, v) not covered do { increase y (u, v) until 3z E {u, v} :xe,x)EEy(z,I) = w(z) stsu {x}Proof of Correctness: (i) At each step, an uncovered edge is found and covered. Thus the algorithm terminates in O(m) steps. (ii) S is a vertex cover, since the algorithm does not terminate until this is true. (iii) y is feasible in the dual LP given in (4), since we start with a feasible y = 0 and at each step increase y(u, v) only to the limit of feasibility. (iv) When adding z to S in the algorithm, the satisfied equality gives us Ce,,,EE y(z,x) = w (z). This value is never altered by the algorithm afterwards, since the algorithm only alters y(u, v) for u @ S and v @ S. Therefore on termination we have Using this statement, we can reexpress the weight of S as (8) is true because each edge can be counted at most twice (once for v = a in the outer sum and once for v = b). (9) was shown to be true in (5). The above algorithm is often referred to as a primal-dual algorithm since it constructs both a (primal) integer solution and a dual solution for the linear programming relaxation. We will now consider a more complicated example based on this primal-dual paradigm. 3 Generalized Steiner Tree Problem Note: Our appromixation solution of the generalized Steiner tree problem will basically be identical to the treatment of the matching problem in the approximation notes, with "generalized Steiner tree problem" substituted for "matching" (and a few other small differences). 3.1 Problem Formulation The generalized Steiner tree problem (GSTP) is: Given a graph with edge costs and a set of pairs of vertices in the graph that you wish to connect, find a minimum cost subgraph where all pairs in the set are connected. Formally: Given a graph G = (V,E),costs c(e) > 0 Ve E E, and vertex pairs T & V x V, find a subgraph F of minimum cost such that V(s,t) E T :s and t are connected in F. GSTP is NP-hard. The best known solution is a 2-approximation algorithm. There are two major variations of GSTP 2-approximation: one is due to Goemans and Williamson, the other to Jain. This lecture will focus mostly on the algorithm of Goemans and Williamson. First, let's formulate GSTP as an integer program: where our objective function is: Min C c(e)x(e) eEEWe can express connectivity for a vertex pair (s, t) E T as follows: Given any s -t cut S,one of the edges in the coboundary (i.e., one of the edges that crosses the cut) must be in F. So if we define the set of all such cuts as F: F= {S: IS n{s,t)l = 1for some (s, t) E T) then we can express the connectivity constraint with one inequality for each set in F,and our GSTP integer program becomes: Min xc(e)x (e) eEE It should be clear that this is a correct formulation of GSTP. If this program yields an infeasible solution for GSTP, then there will be some unsatisfied pair (s,t) E T that is not connected. But this means there is some s -tcut for which no coboundary edge is present in F, which contradicts (10). This integer program solves GSTP, so it is NP-hard. We can make it solvable in polynomial time, however, by applying linear


View Full Document

MIT 6 854J - 6 854J Lecture 17

Download 6 854J Lecture 17
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 6 854J Lecture 17 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 6 854J Lecture 17 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?