CS341 : vertex cover reduction.pdf
Document Summary
We introduce the use linear programming (lp) in the design and analysis of approximation algorithms. the topics include vertex cover, set cover, randomized rounding, dual- tting. It is assumed that the students have some background knowledge in basics of linear programming. Let g = (v, e) be an undirected graph with arc weights w : v r+. Recall the vertex cover problem from previous lecture. We can formulate it as an integer linear programming problem as follows. For each vertex v we have a variable xv. We interpret the variable as follows: if xv = 1 if v is chosen to be included in a vertex cover, otherwise xv = 0. With this interprtation we can easily see that the minimum weight vertex cover can be formulated as the following integer linear program. xv {0, 1} Therefore we use linear programming (lp) to approximate the optimal solution, opt(i), for the integer program.
