Semidefinite Programming: Algorithms in Action for MAX CUT Problem
Learn how Semidefinite Programming is applied in solving the MAX CUT problem efficiently, with insights into Positive Semidefinite Matrices, Linear Semidefinite Programming, LP/SDP algorithms, and more. Discover the motivation behind MAX CUT, its quadratic integer programming formulation, and real-world applications.
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
Algorithms in Action Max Cut using Semidefinite Programming Haim Kaplan, Uri Zwick Tel Aviv University May 2016 Last updated: June 5, 2016 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 approximated using multiplicative updates. Interesting application: Approximation algorithm for MAX CUT
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.
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 12 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 13 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 ? 2 ? ? = min 0 ?<? 1 cos?= 0.87856 1 ?<1 Lower bound on the approximation ratio of the algorithm. 17
cos1? 1 ? 2 ? 18
cos1? 1 ? 2 ? ? 0.689158 ? = cos 1? 2.33112 133.563 19
Is the analysis tight? Yes! The approximation ratio of the algorithm is ???= min 0 ?<? ? [Karloff (1999)] 2 ? 1 cos ?= 0.87856 The integrality gap of the SDP relaxation is also ???. [Feige-Schechtman (1999)]
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)]
