Covering the basic techniques used in the latest research work, the author consolidates progress made so far, including some very recent and promising results, and conveys the beauty and excitement of work in the field. He gives clear, lucid explanations of key results and ideas, with intuitive proofs, and provides critical examples and numerous illustrations to help elucidate the algorithms. Many of the results presented have been simplified and new insights provided. Of interest to theoretical computer scientists, operations researchers, and discrete mathematicians.

key step in the design of an approximation 12.3 Two fundamental algorithm design techniques 101 algorithm. As in the case of the minimum s-t cut problem, a feasible solution to the LP-relaxation can be thought of as a fractional solution to the original problem. However, in the case of an NP-hard problem, we cannot expect the polyhedron defining the set of feasible solutions to have integer vertices. Thus, our task is not to look for an optimal solution to the LP-relaxation, but rather a

leads to an easy proof that this pure strategy attains the same minimum. Thus, R's optimum 0 0 12.5 Notes 107 2:7: strategy is given by maxx minj 1 aijXi. The second critical observation is that the problem of computing R's optimal strategy can be expressed as a linear program: maximize z subject to z- "'a··x· <0 ' ~ •J • - m j = 1, ... ,n i = l, ... ,m i=l m L:xi =1 i=l Xi;:::: 0, Find the dual of this LP and show that it computes the optimal strategy for C. (Use the fact

Xv - e, Xv E V+ { Xv + e, Xv E V_ xv, otherwise. 122 14 Rounding Applied to Set Cover By assumption, v+ u v_ f= 0, and so X is distinct from y and z. Furthermore, x is a convex combination of y and z, since x = ~(y + z). We will show, by choosing c > 0 small enough, that y and z are both feasible solutions for LP (14.2), thereby establishing the lemma. Ensuring that all coordinates of y and z are nonnegative is easy. Next, consider the edge constraints. Suppose Xu + Xv > 1. Clearly, by

the same as the factor 1/2 algorithm. During derandomization, suppose variable x is set first. The conditional expectations are E[W I x =True] = 3 + c/2 and E[W I x =False] = 3 +c. Thus, x will be set to False. But this leads to a total weight of 3 + c, whereas by setting x to True we can get a weight of 4 +c. Clearly, we can get an infinite family 0 of such examples by replicating these 3 clauses with new variables. 16.5 Exercises 16.1 The algorithm of Section 16.1 achieves an approximation

satisfiable. Given a 2CNF= formula F on n Boolean variables, let us define graph G(F) with edge capacities as follows: The graph has 2n vertices, one corresponding to each literal. Corresponding to each clause (p = q) we include the two edges (p, q) and (p, q), each having capacity equal to the weight of the clause (p = q). 176 20 Multicut in General Graphs = = Notice that the two clauses (p q) and (p q) are equivalent. We may assume w.l.o.g. that F does not contain two such equivalent