MIT OpenCourseWare http 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 2008 Approximaion Algorithms MAXCUT Lecturer Michel X Goemans 1 MAX CUT problem MAX CUT Problem Given a graph G V E and weights on the edges w E R nd a cut S S S V that maximizes w S S e S S w e MIN CUT Problem nd a cut S S that minimizes w S S There is a polynomial algorithm for the MIN CUT problem use the min s t cut algorithm on each pair of vertices or better for a xed s and take the smallest of them However the MAX CUT problem is NP hard and we ll try several ways of designing approximation algorithms for it 2 Idea 1 Local Search Algorithm Start from any cut S S De ne the neighborhood N S S of the cut to be the MOVE neighborhood all the cuts that result from moving one vertex from one side of the cut to the other side Consider a locally maximum cut for this neighborhood Lemma 1 If S S is a local maximum for the MOVE neighborhood then w S S 12 w E 1 2 OP T Proof of lemma 1 Look at a vertex i V Let Ci be the set of all edges i j E that are part of the cut S S that is if i S then j S and vice versa Let Ai be the set of all edges i j E that are not part of the cut S S Since moving any single vertex i to the other side of the cut does not improve the weight of the cut we know that w Ci w Ai Summing over all vertices i we get w Ci i V w Ai i V or 2w S S 2w E S S Rearranging we get 4w S S 2w E or w S S 1 1 w E OP T 2 2 Remarks a The bound of 1 2 cannot be improved for this MOVE neighborhood Consider a k vertex cycle where k is a multiple of 4 as the graph G with unit weights The best cut will include Lec18 1 all edges However if we start from a cut in which the edges of the cycle alternate in and out of the cut we have a locally optimum solution with only k 2 edges in the cut b The local search algorithm based on the MOVE neighborhood for MAX CUT takes expo nentially many steps in the worst case This is true even for graphs that are 4 regular each vertex has exactly 4 neighbors Haken and Luby 1 For 3 regular graphs the algorithm is polynomial Poljak 4 c To capture the complexity of local search Johnson Papadimitriou and Yannakakis 3 have de ned the class PLS Polynomial Local Search Members of this class are optimization problems of the form max f x x S together with a neighborhood N S 2S We say that v S is a local optimum if c v max c x x N v To be in PLS we need to have polynomial time algorithms for i nding a feasible solution ii deciding if a solution is feasible and if so computing its cost and iii deciding if a better solution in the neighborhood N v of a solution v exists and if so nding one They introduce a notion of reduction and this leads to PLS complete problems for which any problem in PLS can be reduced to it Their notion of reduction implies that if for one PLS complete problem one has a polynomial time algorithm for nding a local optimum then the same true for all PLS problems In particular MAX CUT with the MOVE neighborhood is PLS complete 5 Furthermore it follows from Johnson et al 3 that the obvious local search algorithm is not an e cient way of nding a local optimum for a PLS complete problem indeed for any PLS complete problem there exist instances for which the local search algorithm of repeatedly nding an improved solution takes exponential time The result of Haken and Luby above is thus just a special case Still this does not preclude other ways of nding a local optimum 3 Idea 2 Random Cut Algorithm There are 2 V possible cuts Sample a cut randomly using a uniform distribution over all possible cuts in the graph v V P r v S 12 independently for all vertices v V Lemma 2 This randomized algorithm gives a cut with expected weight that is 12 OP T Proof of lemma 2 E w S S E w e I e S S e E e E w e P r e S S e E 1 1 w e w E 2 2 Using the method of conditional expectations we can transform this randomized algorithm into a deterministic algorithm The basic idea is to use the following identity for a random variable f and event A E f E f A P r A E f A P r A E f A P r A E f A 1 P r A max E f A E f A In our setting we consider the vertices in a speci c order say v1 v2 and suppose we have already decided conditioned on the position i e whether or not they are in S of v1 vi 1 Now condition on whether vi S Letting f w S S we get E f v1 vi 1 S Ci 1 max E f v1 vi 1 S Ci 1 vi S E f v1 vi 1 S Ci 1 vi S Lec18 2 Both terms in the max can be easily computed and we can decide to put vi on the side of the cut which gives the maximum i e we set Ci to be either Ci 1 or Ci 1 vi in such a way that E f v1 vi 1 S Ci 1 E f v1 vi S Ci When we have processed all inequalities we get a cut Cn C n such that 1 w E E f w Cn C n 2 and this provides a deterministic 0 5 approximation algorithm Examining this derandomized version more closely we notice that we will place vi on the side of the cut that maximizes the total weight between vi and the previous vertices v1 v2 vi 1 This is therefore a simple greedy algorithm Remarks a The performance guarantee of the randomized algorithm is no better than 0 5 just consider the complete graph on n vertices with unit weights Also the performance guarantee of the greedy algorithm is no better than 0 5 int he worst case 4 Idea 3 LP relaxation Algorithm Start from an integer LP formulation of the problem max w e xe e E xe 0 1 e E xe 1 xe C 1 …