Semidefinite Programming for MAX CUT and Coloring

Algorithms in Action Semidefinite Programming based approximation algorithms: MAX CUT and COLORING Haim Kaplan, Uri Zwick Tel Aviv University May 2016 Last updated: June 5, 2018 1

Positive Semidefinite (PSD) Matrices A symmetric ? ? matrix ? is PSD iff: ???? = ?,???,????? 0, for every ? ?. ? = ???, for some ? ? matrix ?. All the eigenvalues of ? are non-negative. There exist real random variables ?1, ,?? such that ? ???? = ??,?. Notation: ? ? iff ? is PSD.

Positive Semidefinite Programming max ? ? s.t. ?? ? ??, ? ? ? 0 ?,?1, ,?? ? ?, ?1, ,?? ? ? = ?,???,???,? (matrix inner product) ? 0 ((symmetric) positive semidefinite) ???? 0 for every ? ? Can be solved exactly using the ellipsoid algorithm. Can be approximated using multiplicative weight updates. Interesting applications: MAX CUT and COLORING

Linear Semidefinite Programming Programming max ? ? s.t. max ? ? s.t. ?? ? ?? ? 0 ?? ? ?? ? 0 Can be solved exactly in polynomial time Can be solved almost exactly in polynomial time

LP/SDP algorithms Simplex method (LP only) Ellipsoid method Interior point methods Algorithms work well in practice, not only in theory! Even faster approximation algorithms using multiplicative weights updates.

Semidefinite Programming (Equivalent formulation Vector Programming) max ??,?(?? ??) ?(?? ??) ?? s.t. ??,? ?? ? The variables are now the vectors ?1,?2, ,??. ? ? iff ? = ???. If ? = [?1?2 ??] then ??,?= ?? ??.

The MAX CUT problem Edges may be weighted

The MAX CUT problem: motivation Given: ? activities, ? persons. Each activity can be scheduled either in the morning or in the afternoon. Each person interested in two activities. Task: schedule the activities to maximize the number of persons that can enjoy both activities. If exactly ?/? of the activities have to be held in the morning, we get MAX BISECTION.

The MAX CUT problem: status Problem is NP-hard Problem is APX-hard (no PTAS unless P=NP) Best approximation ratio known, without SDP, is only 0.5. (Local search, random cut, ) With SDP, an approximation ratio of 0.878 can be obtained! [Goemans-Williamson (1995)] Getting an approximation ratio of 0.942 is NP-hard! (PCP theorem, , [H stad (1997)]) An approximation ration of 0.878 is optimal assuming the Unique Games Conjecture [Khot-Kindler-Mossel-O Donnell (2007)]

A quadratic integer programming formulation of MAX CUT 1 ???? 2 max ??,? s.t. ?? { 1,+1} Left side of the cut Right side of the cut

An SDP Relaxation of MAX CUT [Delorme-Poljak (1993)] [Goemans-Williamson (1995)] 1 ?? ?? 2 max ??,? s.t. ?? ?, ?? ??= 1 This is an SDP, and hence can be solved in polynomial time. The optimal value of the SDP gives an upper bound on the weight of the maximum cut. Can we use an optimal solution of the relaxation to obtain a heavy cut?

An SDP Relaxation of MAX CUT Geometric intuition Embed the vertices of the graph on the unit sphere in ? such that vertices that are joined by edges are far apart.

An SDP Relaxation of MAX CUT Example: ?3 2? 3 ??? = 2 ?? ??= ?? cos2? ?? cos? ??? ???=2 =8 3= 1 9= 0.888 9 4 2 1 1 =9 Integrality ratio 2 ??? = 3 13 2 4

An SDP Relaxation of MAX CUT Another example: ?5 ?4 ?2 2? 5 ?1 ?5 ?3 ??? = 4 Optimal solution lies in 2, even though we are allowed to use 5. ??? ???= 32 = 0.884458 cos4? 5 + 1 4 5= 5 5 + 5 ??? =5 Integrality ratio 5 + 5 14 8

Random hyperplane rounding [Goemans-Williamson (1995)] Choose a random hyperplane passing through the origin. Use the cut defined by the hyperplane!

Choosing a random hyperplane To choose a random hyperplane, choose a random normal vector If ? = ?1,?2, ,?? ?(0,1), independent of each other, then the direction of ? is uniformly distributed over the n-dimensional unit sphere. ?1,?2, ,??, ?

The probability that two vectors are separated by a random hyperplane ? ? ?? ?? ? ?? ? < 0 = If ??,??are unit vectors, ?? ??= cos? ? = cos 1(?? ??) ?? ?

Analysis of the MAX CUT Algorithm [Goemans-Williamson (1995)] cos 1(?? ??) ? Expected weight of the cut obtained using a random hyperplane. ??? = ??,? Value of the SDP relaxation, which is an upper bound on the weight of an optimal cut. 1 ?? ?? 2 ??? = ??,? cos 1? 1 ? ??? ??? min 2 ? = 0.87856 1 ?<1 Lower bound on the approximation ration of the algorithm. 18

cos1? 1 ? 2 ? 19

cos1? 1 ? 2 ? ? 0.689158 ? = cos 1? 2.33112 133.563 20

Is the analysis tight? Yes! [Karloff (1996)] [Feige-Schechtman (2000)]

(Approximate) Graph coloring Given a 3-colorable graph, color it, in polynomial time, using as few colors as possible. Coloring using 4 colours is still NP-hard. [Khanna-Linial-Safra (1993), Khanna-Guruswami (2001)] A simple combinatorial algorithm can color, in polynomial time, using about ? ?1/2colors. [Wigderson (1981)] Using SDP, can color (in poly. time) using ? ?1/4 colors [KMS 95], or even ? ?3/14colors [BK 97].

Coloring 3-colorable graphs using ? ?1/2colors [Wigderson (1981)] A graph with maximum degree can be easily colored using + 1 colors. If < ?1/2, color using + 1 colors. Otherwise, let ? be a vertex of degree hen, ?(?) is 2-colorable and contains an independent set of size ?1/2 2 2

Coloring via independent sets If in any 3-colorable graph of maximum degree we can efficiently find an independent set of size at least then we can efficiently color the graph using ? ? log? colors. ? ? , We repeatedly find independent sets, use a new color to color them and remove them from the graph. After 2? iterations, we colored at least half of the vertices. Repeating this process log? times, we get a full coloring. If we can efficiently find an independent set of size ??, we get a coloring using ? ?1 ?colors. (No log? factor.)

Vector ?-Coloring [Karger-Motwani-Sudan (1995)] A vector ?-coloring of a graph ? = ? = ? ,? is a sequence of unit vectors ?1,?2, ,??such that if ?,? ? then ?? ??= 1 ? 1. The minimum ? for which ? is vector ?-colorable is ? ? (Lov sz s theta function) A vector ?-coloring, if one exists, can be found (approximately) using SDP.

Lemma: If ? = (?,?) is ?-colorable, then it is also vector k-colorable. Proof: There are k unit vectors ?1,?2, ,?? such that ?? ??= 1 ? 1, for ? ?. ? = 3 :

Finding large independent sets [Karger-Motwani-Sudan (1995)] Let ? be a random normally distributed 2 3ln . vector in ?. Let ? = ? = ? ? | ?? ? ? ? is obtained from ? by removing a vertex from each edge in ?.

Finding large independent sets [Karger-Motwani-Sudan (1995)] ?? ? ??

Analysis Let ? and ? be the number of vertices and edges in ?. ? ? ? For every ?, we have ?? ? ?(0,1). If ?,? ? then ?? ??= 1 2= ??+ ?? ??+ ?? = ?? For every ?,? ?, we have (??+??) ? ?(0,1). 2and 2= 1. 2+ 2?? ??+ ?? ??+ ?? ? ? = ? ?1 ? ? = ? ?(?) ? ? = ? ?1 ? ? and ?2 ? ? ? ?1+ ?2 ? 2? = ? ?(2?) ? ? ? ? ? ? ? ? ? ?(2?)

Analysis Let be the maximum degree. Of course ? ? 2. ? ? ? ? ? 2? ? ? ? ? ? ? ? ? 2? 2? 1 2? ? ?2/2?? ? ? = ? ? 0,1 ? = ? 1 1 1 ? 1 1 ?? ?2/2 ?3? ?2/2 ? ? 2? 2? 2 3ln , so ? ?2/2= 1/3. Recall that ? = We show that ? 2? ?(?). Therefore, ? ? 1 ? . 2? ? ? = 1/3ln

Analysis We show that ? 2? ?(?). ?3? ?2 1 ? 1 1 2?? 2?2 2 ? 3?2 ? ? ? 2? 2 = ? Thus, we get an independent set of size . 1/3ln Over all, we get a randomized polynomial time algorithm that colors a 3-colorable graph of maximum degree using ? 1/3log log? colors.

Coloring ?-colorable graphs Coloring k-colorable graphs using min{ 1-2/k,n1-3/(k+1) } colors. [Karger-Motwani-Sudan (1995)] Coloring 3-colorable graphs using n3/14colors. [Blum-Karger (1997)]