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.2 18.415/6.854 Advanced Algorithms 28 November 2001 Lecture 20 Lecturer: Michel X. Goernans Scribe: David Liben-Nowell and Bill Thies Review In the previous lecture, we were considering the LIN-2-MOD-2 problem, which is as follows. We are given a set of equations, and our goal is to satisfy as many of them as possible: xi +Xj {0,1) (mod 2) That is, each equation states that the sum of exactly two variables is congruent (modulo 2) to either 0 or 1. Restricting our attention to the case when each sum is congruent to 1, this problem is equivalent to the following instance of MAX-CUT. Given a graph G = (V,E) with a vertex u for each variable x and an edge (vi, ~j)for each equation xi +xj 1 (mod 2), find the set of vertices S C V that maximizes the number of edges crossing the boundary of the set: max d(S)scv where d(S) = IS(S)I is the number of edges crossing -&.om S to V \ S We then established the following upper bound (UB) for MAX-CUT: We will refer to this maximization problem as SDP, which stands for "semi-definite programming" as we will see later. In the case when p = 1, UB is clearly equal to the value of the maximum cut; we showed that for larger p, the expression above still remains an upper bound. Finally, we used this expression to sketch out a 0.878-approximation algorithm for MAX-CUT. In this lecture, we formulate the details of this algorithm and prove its correctness. A 0.878-Approximation Algorithm for Max-Cut The 0.878-approximation algorithm that we consider is due to Goemans and Williamson [2]. An outline of the algorithms is as follows: Algorithm for Max-Cut : 1. Solve the SDP problem (Equation 3) to obtain vectors vi. 2. We'd like to separate the vectors into two groups that are "maximally separated" in order to determine the cut S c V. As discussed in the last lecture, we can do this with a hyperplane in RP, and split the vectors based on which side of the hyperplane they fall. However, since we can rotate all of the vectors vi without changing the goodness of the solution, it is not a good idea to fix a single hyperplane to do this separation since some cases will elicit a poor split. Instead, we select a unit vector r uniformly at random from the p-dimensional sphere Sp-l = {x E RP : llxll = 1). (We denote this sphere by Sp-l since Sl is a circle in two dimensions.)Figure I: One can select a point uniformly at random from the surface of S2,the three-dimensional unit sphere, by choosing uniformly at random 8 from [0,2;lr]and h from [-I, 11and then projecting the point horizontally onto the surface of the sphere. 3. Select the cut S as those vectors which fall on one side of r: S = {i E V : r vi 4 0). There are three issues in the above algorithm that we need to address. In Section 5, we present a method for solving the SDP problem as required in step 1. In Section 3 we show how to randomly select the unit vector r as required in step 2, and in Section 4 we analyze selection of the cut to show that it is, in fact, a 0.878-approximation algorithm. 3 Choosing a Random Vector It is not entirely trivial to choose a vector that is uniformly distributed across the points of a multi-dimensional sphere. For instance, in three dimensions, choosing both latitude and longitude coordinates uniformly at random will not yield points that are uniformly distributed across the surface of the earth. This is because a given range of latitude covers a smaller and smaller portion of the earth's surface as one nears the poles-thus, if latitude were chosen uniformly, more points would end up near the poles than near the equator. 3.1 3-D Solution For the case of three dimensions, a uniform spherical distribution can be obtained by choosing different coordinates uniformly at random. These coordinates are 1) an angle 8 E [O,27r]and 2) a height h E [-I, 11. The random vector can then be obtained by projecting horizontally onto a sphere from the corresponding position on an enclosing cylinder (see Figure 1). In other words, one can take 8 as the longitude and asin(h) as the latitude. 3.2 General Solution In the general case, one can generate r from Sp-l uniformly at random by choosing each coordinate according to N(0,I),the normal distribution with mean 0 and standard deviation 1. Using oc to denote proportionality, we have by the definition of a normal distribution that: We can see that this gives the desired result if we consider the normal distribution in p dimensions: f (XI,x2,...xp) ce-+(x:+":+-.-+x;) (5)Figure 2: Two vectors ui and uj with rin, the component of the random vector r which lies in the plane of ui and uj. where c denotes some constant. Noting that the distance of any point from the origin is d = we can see that the distribution depends only on d instead of the position along any given axis: -4d2f (dl ce (6) Thus, selecting each coordinate from this distribution will give vectors that are uniformly distributed within the unit sphere Sp-l. 4 Analyzing the Algorithm We now turn our attention to proving that our choice of S = {i E V : r . ui > 0) does yield a 0.878-approximation algorithm for MAX-CUT,given that vi are a solution to SDP (Equation 3) and r is chosen randomly as described above. As a first step, we will need a closed form expression for the expected value of the cut, given our random choice of r. For this, we turn to the following theorem: Theorem 1 For any set of unit vectors Vi, E[d(S)] = tEx{i,j) Proof: Let us introduce an indicator variable Iijwhose value is 1 if (i,j) is in the cut and 0 otherwise. Then we have that, by the definition of d and of expectation: Now let us consider this last probability-that exactly one of a pair of vertices i and j are contained in S. This will be the case if the unit vectors ui and uj were separated by the hyperplane orthogonal to our random vector r. Let us split r up into two components: 1)rin,the component that is in the plane of vi and vj, and 2) rout,the component that is orthogonal to ui and uj. We are not concerned with rout because its dot product with ui and uj is zero; therefore, our decision as to whether or not to include i and j in S depends only on ri,. Thus, we restrict