Approximation Algorithms and Semidefinite Programming Bernd Ga¨rtner • Jiˇr´ı Matousˇek Approximation Algorithms and Semidefinite Programming 123 BerndGa¨rtner Jiˇr´ıMatousˇek ETHZurich CharlesUniversity InstituteofTheoreticalComputerScience DepartmentofAppliedMathematics 8092Zurich Malostranske´na´m.25 Switzerland 11800Prague1 [email protected] CzechRepublic [email protected] ISBN978-3-642-22014-2 e-ISBN978-3-642-22015-9 DOI10.1007/978-3-642-22015-9 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2011943166 MathematicsSubjectClassification(2010):68W25,90C22 (cid:2)c Springer-VerlagBerlinHeidelberg2012 Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation,broadcasting, reproductiononmicrofilmorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9, 1965,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violations areliabletoprosecutionundertheGermanCopyrightLaw. Theuseofgeneral descriptive names,registered names, trademarks, etc. inthis publication does not imply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotective lawsandregulationsandthereforefreeforgeneraluse. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface This text, based on a graduate course taught by the authors, introduces the reader to selected aspects of semidefinite programming and its use in approximationalgorithms.Itcoversthebasicsaswellasasignificantamount of recent and more advanced material, sometimes on the edge of current research. Methods based on semidefinite programming have been the big thing in optimization since the 1990s, just as methods based on linear programming had been the big thing before that – at least this seems to be a reasonable picturefromthepointofviewofacomputerscientist.Semidefiniteprograms constitute one of the largest classes of optimization problems that can be solved reasonably efficiently – both in theory and in practice. They play an important role in a variety of research areas, such as combinatorial opti- mization, approximation algorithms, computational complexity, graph the- ory, geometry, real algebraic geometry, and quantum computing. We develop the basic theory of semidefinite programming; we present one of the known efficient algorithms in detail, and we describe the principles of some others. As for applications, we focus on approximation algorithms. There are many important computational problems, such as MaxCut,1 for which one cannot expect to obtain an exact solution efficiently, and in such cases one has to settle for approximate solutions. The maintheoretical goalin this situationis to find efficient(polynomial- time)algorithmsthatalwayscomputeanapproximatesolutionofsomeguar- anteedquality.Forexample,ifanalgorithmreturns,foreverypossibleinput, a solutionwhose qualityis atleast87%ofthe optimum, we saythatsuchan algorithm has approximation ratio 0.87. In the early 1990s it was understood that for MaxCut and several other problems, a method based on semidefinite programming yields a bet- ter approximation ratio than any other known approach. But the question 1 Dividingthevertex setof agraph intotwoparts interconnected byas many edges as possible. v vi Preface remained, could this approximation ratio be further improved, perhaps by some new method? For several important computational problems, a similar question was solved in an amazing wave of progress, also in the early 1990s: the best approximationratioattainablebyany polynomial-timealgorithm(assuming P(cid:2)=NP) was determined precisely in these cases. For MaxCut and its relatives, a tentative but fascinating answer came considerably later. It tells us that the algorithms based on semidefinite pro- gramming deliver the best possible approximation ratio, among all possible polynomial-time algorithms. It is tentative since it relies on an unproven (butappealing)conjecture,theUniqueGamesConjecture(UGC).Butifone believes in that conjecture, then semidefinite programming is the ultimate tool for these problems – no other method, known or yet to be discovered, can bring us any further. We will follow the “semidefinite side” of these developments, presenting some of the main ideas behind approximation algorithms based on semidefi- nite programming. The origins of this book. Whenwewroteathinbookonlinearprogram- ming some yearsago,Nati Linial told us that we should include semidefinite programming as well. For various reasons we did not, but since one should trust Nati’s fantastic instinct for what is, or will become, important in theo- retical computer science, we have kept that suggestion in mind. In 2008, also motivated by the stunning progress in the field, we decided togiveacourseonthetopicsofthepresentbookatETHZurich.Sowecame to the question, what should we teach in a one-semester course? Somewhat naively, we imagined we could more or less use some standard text, perhaps with a few additions of recent results. Tomakealongstoryshort,wehavenotfoundanydirectlyteachabletext, standard or not, that would cover a significant part of our intended scope. So weended upreadingstacksofresearchpapers,producing detailedlecture notes, and later reworking and publishing them. This book is the result. SomeFAQs. Q: Whyaretheretwopartsthatlooksodifferentintypography and style? A: Each of the authors wrote one of the parts in his own style. We have not seensufficiently compelling reasonsfor trying to unify the style. Also see the next answer. Q: Why does the second part have this strange itemized format – is it just some kind of a draft? A: Itisnotadraft;ithasbeenproofreadandpolishedaboutasmuchasother booksofthesecondauthor.Theunusualformisintentional;the(experimen- tal)ideaistosplitthematerialintosmallandhierarchicallyorganizedchunks of text. This is based on the author’s own experience with learning things, as well as on observing how others work with textbooks. It should make the Preface vii text easier to digest (for many people at least) and to memorize the most importantthings. It probablyreadsmoreslowly, but itis alsomorecompact than a traditional text. The top-level items are systematically numbered for aneasyreference.Ofcourse,thereadersareinvitedtoformtheirownopinion on the suitability of such a presentation. Q: Why haven’t you included many more references and historical remarks? A: Our primary goal is to communicate the key ideas. One usually does not provide the students with many references in class, and adding survey- style references would change the character of the book. Several surveys are available,andreaderswhoneedmoredetailedreferencesorabetteroverview ofknownresultsona particulartopic shouldhavenogreatproblemslooking them up given the modern technology. Q: Why don’t you cover more about the Unique Games Conjecture and inap- proximability, which seems to be one of the main and most exciting research directions in approximation algorithms? A: Our main focus is the use of semidefinite programming, while the UGC concerns lower bounds (inapproximability). We do introduce the conjecture and cite results derived from it, but we have decided not to go into the technical machinery around it, mainly because this would probably double the current size of the book. Q: Why is topic X not covered? How did you select the material? A: We mainly wanted to build a reasonable course that could be taught in one semester. In the current flood of information, we believe that less mate- rialisoftenbetterthanmore.Wehavetriedtoselectresultsthatweperceive as significant, beautiful, and technically manageable for class presentation. One of our criteria was also the possibility of demonstrating various general methods of mathematics and computer science in action on concrete exam- ples. Sources. As basic sources of information on semidefinite programming in general one can use the Handbook of Semidefinite Programming [WSV00] and the surveys by Laurent and Rendl [LR05] and Vandenberghe and Boyd [VB96].Thereisalsoabrandnewhandbookinthemaking[AL11].Thebooks byBen-TalandNemirovski[BTN01]andbyBoydandVandenberghe[BV04] areexcellentsourcesaswell,withasomewhatwiderscope.Thelecturenotes by Ye [Ye04] may also develop into a book in the near future. A new extensive monograph on approximation algorithms, including a significant amount of material on semidefinite programming, has recently been completed by Williamson and Shmoys [WS11]. Another source worth mentioning are Lov´asz’ lecture notes on semidefinite programming [Lov03], beautiful as usual but not including recent results. Lots of excellent material can be found in the transient world of the Internet, often in the form of slides or course notes. A site devoted to semidefinite programming is maintained by Helmberg viii Preface [Hel10], and another current site full of interesting resources is http:// homepages.cwi.nl/~monique/ow-seminar-sdp/by Laurent. We have par- ticularly benefited from slides by Arora (http://pikomat.mff.cuni. cz/honza/napio/arora.pdf), by Feige (http://www.wisdom.weizmann. ac.il/~feige/Slides/sdpslides.ppt), by Zwick (www.cs.tau.ac.il/ ~zwick/slides/SDP-UKCRC.ppt), and by Raghavendra (several sets at http://www.cc.gatech.edu/fac/praghave/). A transient world indeed – some of the materials we found while preparing the course in 2009 were no longer on-line in mid-2010. For recentresults aroundthe UGC andinapproximability, one ofthe best sources known to us is Raghavendra’s thesis [Rag09]. The DIMACS lecture notes [HCA+10] (with 17 authors!) appearedonly after our book was nearly finished, and so did two nice surveys by Khot [Kho10a,Kho10b]. In another direction, the lecture notes by Vallentin [Val08] present inter- actions of semidefinite programming with harmonic analysis, resulting in remarkableoutcomes.VeryenlighteningcoursenotesbyParrilo[Par06]treat theuseofsemidefiniteprogrammingintheoptimizationofmultivariatepoly- nomials and such. A recent book by Lasserre[Las10] also covers this kind of topics. Prerequisites. We assume basic knowledge of mathematics from standard undergraduate curricula; most often we make use of linear algebra and basic notions of graph theory. We also expect a certain degree of mathematical maturity,e.g., the ability tofill in routinedetails incalculationsorinproofs. Finally, we do not spend much time on motivation, such as why it is inter- esting and important to be able to compute good graph colorings – in this respect, we also rely on the reader’s previous education. Acknowledgments. We would like to thank Sanjeev Arora, Michel Baes, Nikhil Bansal, Elad Hazan, Martin Jaggi, Nati Linial, Prasad Raghavendra, Tama´sTerlaky,DominikScheder,andYinyuYeforusefulcomments,sugges- tions, materials, etc., Helena Nyklov´a for a great help with typesetting, and Ruth Allewelt, Ute McCrory, and Martin Peters from Springer Heidelberg for a perfect collaboration (as usual). Errors. If you find errors in the book, especially serious ones, we would appreciate it if you would let us know (email: [email protected], [email protected]). We plan to post a list of errors at http://www. inf.ethz.ch/personal/gaertner/sdpbook. Contents Part I (by Bernd G¨artner) 1 Introduction: MAXCUT Via Semidefinite Programming ... 3 1.1 The MaxCut Problem ................................. 3 1.2 Approximation Algorithms .............................. 4 1.3 A Randomized 0.5-ApproximationAlgorithm for MaxCut .. 6 1.4 The Goemans–Williamson Algorithm ..................... 7 2 Semidefinite Programming................................ 15 2.1 From Linear to Semidefinite Programming................. 15 2.2 Positive Semidefinite Matrices............................ 16 2.3 Cholesky Factorization .................................. 17 2.4 Semidefinite Programs .................................. 18 2.5 Non-standard Form..................................... 20 2.6 The Complexity of Solving Semidefinite Programs .......... 20 3 Shannon Capacity and Lov´asz Theta...................... 27 3.1 The Similarity-Free Dictionary Problem ................... 27 3.2 The Shannon Capacity.................................. 29 3.3 The Theta Function .................................... 31 3.4 The Lov´asz Bound...................................... 32 3.5 The 5-Cycle ........................................... 35 3.6 Two Semidefinite Programs for the Theta Function ......... 36 3.7 The Sandwich Theorem and Perfect Graphs ............... 39 4 Duality and Cone Programming .......................... 45 4.1 Introduction ........................................... 45 4.2 Closed Convex Cones ................................... 47 4.3 Dual Cones ............................................ 49 4.4 A Separation Theorem for Closed Convex Cones............ 51 4.5 The Farkas Lemma, Cone Version ........................ 52 ix