Semidefinite Programming for Max-Cut Problem
Semidefinite programming as a powerful tool for solving the max-cut problem in graph theory. Understand the formulation, constraints, and optimization strategies involved in this critical area of algorithm design and analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CMPT 405/705 Design & Analysis of Algorithms April 6, 2022
Plan for today Semidefinite Programming: 0.878-approximation for Max-Cut
Semi-definite Programming *This topic is hard, and I don t understand it, so don t ask me questions **That was a joke
Semidefinite programming Consider the max-cut problem: Input: A graph G = (V,E) Output: A cut (S,V\S) in G that maximizes the number of edges E[S,V\S].
Semidefinite programming Consider the max-cut problem: Input: A graph G = (V,E) Output: A cut (S,V\S) in G that maximizes the number of edges E[S,V\S]. Let s try to write an LP. xv {0,1} yuv {0,1} for all v V for all (u,v) E We can t implement the constraints yu,v = |xu-xv| Maximize e E ye for all v V for all e E for all (u,v) E Subject to 0 xv 1 0 ye 1 yu,v= |xu-xv|
Semidefinite programming Input: A graph G = (V,E) Output: A cut (S,V\S) in G that maximizes the number of edges E[S,V\S]. Let s try to write not-an-LP. If xu=xv then yuv=1 Otherwise, yuv=-1 Intention: xv {-1,1} for all v V This really captures max-cut. But xu s are not really part of the LP for all u,v V LP: yuv = xvxu Maximize (u,v) E (1-yu,v) // =1 if yu,v=-1 // =0 if yu,v=-1 for all (u,v) E for all v V Subject to yu,v = yv,u yv,v = 1
Semidefinite programming Input: A graph G = (V,E) Output: A cut (S,V\S) in G that maximizes the number of edges E[S,V\S]. LP: variables {yu,v : u,v V} xv {-1,1} yuv = xvxu for all v V for all (u,v) E Maximize (u,v) E (1-yu,v) for all (u,v) E for all v V Subject to yu,v = yv,u yv,v = 1 The LP can return a solution yu,v = -1000000 for all (u,v) E, and yv,v = 1 for v V That gives a huge LP value, but this is not very informative
Semidefinite programming Input: A graph G = (V,E) Output: A cut (S,V\S) in G that maximizes the number of edges E[S,V\S]. LP: variables {yu,v : u,v V} xv {-1,1} yuv = xvxu for all v V for all (u,v) E Maximize (u,v) E (1-yu,v) for all (u,v) E for all v V Subject to yu,v = yv,u yv,v = 1 How can we avoid the solution yu,v = -1000000 for all (u,v) E, and yv,v = 1 for v V To avoid this we can add a constraint u,v yuv 0 Why? Because u,v yuv = u,v xuxv = ( u V xu) ( v V xv)= ( v V xv)2 0
Semidefinite programming xv {-1,1} yuv = xvxu for all v V for all (u,v) E LP: variables {yu,v : u,v V} Maximize (u,v) E (1-yu,v) for all (u,v) E for all v V Subject to yu,v = yv,u yv,v = 1 u,v VxV yuv 0 Can we add more constraints? For example, we avoid the solution with y1,2=y1,2=-1,000,000, and yu,v=1 otherwise? This implies that y12 -1 Because y11=y22=1 and y12= y21 We can add the constraint (y1,1 + y1,2 + y2,1 + y2,2) 0 Why? Because y1,1 + y1,2 + y2,1 + y2,2 = (x1x1 + x1x2 + x2x1 + x2x2)= (x1+x2)2 0
Semidefinite programming xv {-1,1} yuv = xvxu for all v V for all (u,v) E LP: variables {-1 yu,v 1: u,v V} Maximize (u,v) E (1-yu,v) for all (u,v) E Subject to yu,v = yv,u yv,v = 1 for all v V u,v VxV yuv 0 yi,i yi,j yj,i + yj,j 0 And we can add more constraints of the form (c1x1+c2x2+ cnxn)2 0 This corresponds to i,j VxV cicjyi,j=(c1x1+c2x2+ cnxn)2 0 In fact, we can add all such constraints for all {ci : i V} R|V|
Semidefinite programming xv {-1,1} yuv = xvxu for all v V for all (u,v) E LP: variables {-1 yu,v 1: u,v V} Maximize (u,v) E (1-yu,v) for all (u,v) E Subject to yu,v = yv,u yv,v = 1 for all v V u,v VxV cucvyuv 0 (*) (*) is equivalent to {yu,v} being a matrix Y RVxV, such that cTYc 0 for all c RV Fact: this (infinite) LP can be solved in poly(n) time
Semidefinite programming xv {-1,1} yuv = xvxu for all v V for all (u,v) E LP: variables {-1 yu,v 1: u,v V} Maximize (u,v) E (1-yu,v) for all (u,v) E for all v V Subject to yu,v = yv,u yv,v = 1 u,v VxV cucvyuv 0 (*) (*) is equivalent to {yu,v} being a matrix Y RVxV, such that cTYc 0 for all c RV c1 y11 y12 y13 y14 c2 y21 y22 y23 y24 c3 y31 y32 y33 y34 c1 c2 c3 c4 c4 y41 y42 y43 y44
Semidefinite programming Definition: A symmetric matrix Y Rnxn is called positive semi-definite (Y 0) if cTYc 0 for all c Rn. Facts: Fix a symmetric matrix Y Rnxn. The following are equivalent Y is positive semi-definite, i.e., cTYc 0 for all c Rn. 1) 2) All eigenvalues of Y are non-negative There is a matrix U Rnxn such that Y=UTU. 3) There are x1 xn Rn such that Yi,j = <xi,xj> (inner product of the vectors) 4) Theorem: Any LP over n2 variables arranged in a matrix with the (infinitely many) SDP constraints can be solved efficiently. Furthermore, we can efficiently find xi Rn as in 4) satisfying the constraints.
Semidefinite programming Theorem: An LP over n2 variables arranged in a nxn matrix with the (infinitely many) SDP constraints can be solved efficiently. Furthermore, we can efficiently find xi Rn such that {yi,j = <xi,xj>} satisfy the LP. Fine print: SDPs can be solved up to additive error of in time poly(n*log(1/ ))
0.878-approximation for Max-Cut Our goal for today: Theorem[Goemans-Williamson 94]: Max-Cut admits a 0.878 approximation algorithm. In HW4 you saw a 0.5-approximation by taking a random cut.
0.878-approximation for Max-Cut Theorem[Goemans-Williamson 94]: Max-Cut admits a 0.878 approximation algorithm. 0.5-approximation is trivial by taking a random cut. The SDP based algorithm does better Q: What is this mysterious 0.878 number? arccos(?)/? 1 2 ? A: It is min 1 ? 1 2 Well, that doesn t really help, does it?
0.878-approximation for Max-Cut Input: A graph G = (V,E) Output: A cut (S,V\S) in G that maximizes the number of edges E[S,V\S]. Let s try to write an SDP. Variables: xv Rn for all v V Maximize (u,v) E (1 - <xu,xv>) for all v V Subject to ||xv||=1 We get an SDP solution. Observation: SDP-value max-cut(G) Proof: For any integral solution S, V\S define the SDP solution by setting xv=e1 for all v S, and. xv=-e1 for all v V\S, and.
0.878-approximation for Max-Cut Input: A graph G = (V,E) Output: A cut (S,V\S) in G that maximizes the number of edges E[S,V\S]. Let s try to write an SDP. Variables: xv Rn for all v V Maximize (u,v) E (1 - <xu,xv>) for all v V Subject to ||xv||=1 We get an SDP solution. The intention is Then, we can set S to be the orange vertices, and V\S the blue vertices.
0.878-approximation for Max-Cut Input: A graph G = (V,E) Output: A cut (S,V\S) in G that maximizes the number of edges E[S,V\S]. Let s try to write an SDP. Variables: xv Rn for all v V Maximize (u,v) E (1 - <xu,xv>) for all v V Subject to ||xv||=1 We get an SDP solution. How should we round this SDP solution?
0.878-approximation for Max-Cut Maximize (u,v) E (1-<xu,xv>) for all v V Subject to ||xv||=1 We get an SDP solution. Rounding procedure: 1. Choose a random hyperplane 2. Partition the vertices by letting S = {v V : xv is above the hyperplane} V\S = {v V : xv is below the hyperplane}
0.878-approximation for Max-Cut Q1: How can we choose a random hyperplane in Rn. A1: The standard way to do it is to do it is the following: Choose r1,r2 rn R according to N(0,1) 1. 2? ? ?2 1 2. That is the probability density function is 2 Let r = (r1,r2 rn) Rn 3. 4. Let H = {x : <x,r> = 0} Fact: The distribution of r is spherically symmetric. S = {u V : <xu,r> 0} vectors above the hyperplane V\S = {u V : <xu,r> < 0} vectors below the hyperplane Then, and
0.878-approximation for Max-Cut Q: How can we sample r1,r2 rn R according to N(0,1)? 2? ? ?2 1 That is the probability density function is 2 Choose a uniform s [0,1], and output ri such that Pr[N(0,1) r] = s.
0.878-approximation for Max-Cut Maximize (u,v) E (1-<xu,xv>) for all v V Subject to ||xv||=1 Solve the SDP Round the SDP solution using a random hyperplane Let us compute the expected value of the cut E[value of the cut] = (u,v) EE[1(u,v) is in the cut]= (u,v) EPr[(u,v) is in the cut] We want to compare it to the SDP value, which is (u,v) E (1 - <xu,xv>) We want to show that E[value of the cut] 0.878*( (u,v) E (1 - <xu,xv>))
0.878-approximation for Max-Cut Claim: Pr[(u,v) is in the cut] = arccos(<xu,xv>))/ Proof: Observe that Pr[(u,v) is in the cut] is proportional to the angle between xu and xv That is, Pr[(u,v) is in the cut] = angle between xu,xv / = arccos(<??,??>) ? Therefore arccos(<??,??>) ? E size of the cut = ?,? ? How do we compare this to the SDP value ?,? ?(1 2 <??,??> )? 2
0.878-approximation for Max-Cut arccos(<??,??>) ? We have E size of the cut = ?,? ? SDP value ?,? ?(1 2 <??,??> ). 2 arccos(?)/? 1 2 ? Let ???:= min = 0.878 1 ? 1 2 Then E size of the cut ??? ???????? Since ??? ????? ??? ???(?), we conclude that the algorithms is a 0.878-approximation for max-cut, i.e., ? size of the cut ??? ???(?) ???.
0.878-approximation for Max-Cut Theorem[Goemans-Williamson 94]: Max-Cut admits a ???-approximation algorithm, for ???= min 1 ? 1 2 arccos(?)? 1 2 ? =0.878. Facts: Assuming the Unique games conjecture it is NP-hard to approximated max-cut within a factor ???+ ? for any ? > 0. [Khot, Kindler, Mossel, O Donnell 05] [Mossel, O Donnell, Oleszkiewicz 05] Without the unique games conjecture, it is NP-hard to approximate max-cut withing a factor of 16/17=0.941... A closely related problem: Max-bisection Best known algorithm gives 0.877-approximation. Conjecture: Max-bisection admits a ???-approximation algorithms HW: Prove that if we have an ?-approximation for Max-Bisection, then we also have an ?-approximation for Max-Cut.
Questions? Comments?
