Vijay V. Vazirani College of Computing Georgia Institute of Technology Copyright (cid:1)c 2001 Approximation Algorithms Springer Berlin Heidelberg NewYork Barcelona HongKong London Milan Paris Singapore Tokyo To my parents Preface Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872–1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed con- jecture that P (cid:2)= NP, their exact solution is prohibitively time consuming. Chartingthelandscapeofapproximabilityoftheseproblems,viapolynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of ap- proximation algorithms as it stands today. It is reasonable to expect the picture to change with time. The book is divided into three parts. In Part I we cover a combinato- rial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected – nature is very rich, and we cannot expect a few tricks to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly cat- egorizing algorithmic techniques so as not to trivialize matters. Instead, we haveattemptedtocapture,asaccuratelyaspossible,theindividualcharacter ofeachproblem,andpointoutconnectionsbetweenproblemsandalgorithms for solving them. In Part II, we present linear programming based algorithms. These are categorized under two fundamental techniques: rounding and the primal– dual schema. But once again, the exact approximation guarantee obtainable depends on the specific LP-relaxation used, and there is no fixed recipe for discoveringgoodrelaxations,justasthereisnofixedrecipeforprovingathe- orem in mathematics (readers familiar with complexity theory will recognize this as the philosophical point behind the P(cid:2)=NP question). Part III covers four important topics. The first is the problem of finding a shortest vector in a lattice which, for several reasons, deserves individual treatment (see Chapter 27). The second topic is the approximability of counting, as opposed to optimization, problems (counting the number of solutions to a given in- stance). The counting versions of all known NP-complete problems are #P- complete1. Interestingly enough, other than a handful of exceptions, this is true of problems in P as well. An impressive theory has been built for ob- 1 However, there is no theorem to this effect yet. VIII Preface tainingefficientapproximatecountingalgorithmsforthislatterclassofprob- lems. Most of these algorithms are based on the Markov chain Monte Carlo (MCMC) method, a topic that deserves a book by itself and is therefore not treated here. In Chapter 28 we present combinatorial algorithms, not using the MCMC method, for two fundamental counting problems. The third topic is centered around recent breakthrough results, estab- lishing hardness of approximation for many key problems, and giving new legitimacy to approximation algorithms as a deep theory. An overview of these results is presented in Chapter 29, assuming the main technical theo- rem, the PCP Theorem. The latter theorem, unfortunately, does not have a simple proof at present. The fourth topic consists of the numerous open problems of this young field. The list presented should by no means be considered exhaustive, and is moreover centered around problems and issues currently in vogue. Exact algorithms have been studied intensively for over four decades, and yet basic insights are still being obtained. Considering the fact that among natural computational problems, polynomial time solvability is the exception rather than the rule, it is only reasonable to expect the theory of approximation algorithms to grow considerably over the years. The set cover problem occupies a special place, not only in the theory of approximationalgorithms,butalsointhisbook.Itoffersaparticularlysimple setting for introducing key concepts as well as some of the basic algorithm designtechniquesofPartIandPartII.Inordertogiveacompletetreatment for this central problem, in Part III we give a hardness result for it, even though the proof is quite elaborate. The hardness result essentially matches the guarantee of the best algorithm known – this being another reason for presenting this rather difficult proof. Our philosophy on the design and exposition of algorithms is nicely il- lustrated by the following analogy with an aspect of Michelangelo’s art. A major part of his effort involved looking for interesting pieces of stone in the quarry and staring at them for long hours to determine the form they natu- rallywantedtotake.Thechiselworkexposed,inaminimalisticmanner,this form. By analogy, we would like to start with a clean, simply stated problem (perhaps a simplified version of the problem we actually want to solve in practice). Most of the algorithm design effort actually goes into understand- ing the algorithmically relevant combinatorial structure of the problem. The algorithmexploitsthisstructureinaminimalisticmanner.Theexpositionof algorithmsinthisbookwillalsofollowthisanalogy,withemphasisonstating the structure offered by problems, and keeping the algorithms minimalistic. An attempt has been made to keep individual chapters short and simple, often presenting only the key result. Generalizations and related results are relegatedtoexercises.Theexercisesalsocoverotherimportantresultswhich could not be covered in detail due to logistic constraints. Hints have been Preface IX provided for some of the exercises; however, there is no correlation between the degree of difficulty of an exercise and whether a hint is provided for it. Thisbookissuitableforuseinadvancedundergraduateandgraduatelevel courses on approximation algorithms. It has more than twice the material thatcanbecoveredinasemesterlongcourse,therebyleavingplentyofroom for an instructor to choose topics. An undergraduate course in algorithms and the theory of NP-completeness should suffice as a prerequisite for most of the chapters. For completeness, we have provided background information on several topics: complexity theory in Appendix A, probability theory in AppendixB,linearprogramminginChapter12,semidefiniteprogrammingin Chapter26,andlatticesinChapter27.(Adisproportionateamountofspace has been devoted to the notion of self-reducibility in Appendix A because this notion has been quite sparsely treated in other sources.) This book can also be used is as supplementary text in basic undergraduate and graduate algorithms courses. The first few chapters of Part I and Part II are suitable for this purpose. The ordering of chapters in both these parts is roughly by increasing difficulty. Inanticipationofthiswideaudience,wedecidednottopublishthisbook in any of Springer’s series – even its prestigious Yellow Series. (However, we could not resist spattering a patch of yellow on the cover!) The following translations are currently planned: French by Claire Kenyon, Japanese by Takao Asano, and Romanian by Ion Ma˘ndoiu. Corrections and comments from readers are welcome. We have set up a special email address for this purpose: [email protected]. Finally, a word about practical impact. With practitioners looking for high performance algorithms having error within 2% or 5% of the optimal, what good are algorithms that come within a factor of 2, or even worse, O(logn), of the optimal? Further, by this token, what is the usefulness of improving the approximation guarantee from, say, factor 2 to 3/2? Letusaddressbothissuesandpointoutsomefallaciesintheseassertions. The approximation guarantee only reflects the performance of the algorithm on the most pathological instances. Perhaps it is more appropriate to view the approximation guarantee as a measure that forces us to explore deeper into the combinatorial structure of the problem and discover more powerful tools for exploiting this structure. It has been observed that the difficulty of constructing tight examples increases considerably as one obtains algo- rithms with better guarantees. Indeed, for some recent algorithms, obtaining a tight example has been a paper by itself (e.g., see Section 26.7). Experi- ments have confirmed that these and other sophisticated algorithms do have error bounds of the desired magnitude, 2% to 5%, on typical instances, even though their worst case error bounds are much higher. Additionally, the the- oretically proven algorithm should be viewed as a core algorithmic idea that needstobefinetunedtothetypesofinstancesarisinginspecificapplications. X Preface Wehopethatthisbookwillserveasacatalystinhelpingthistheorygrow and have practical impact. Acknowledgments This book is based on courses taught at the Indian Institute of Technology, DelhiinSpring1992andSpring1993,atGeorgiaTechinSpring1997,Spring 1999,andSpring2000,andatDIMACSinFall1998.TheSpring1992course resulted in the first set of class notes on this topic. It is interesting to note that more than half of this book is based on subsequent research results. Numerous friends – and family members – have helped make this book a reality. First, I would like to thank Naveen Garg, Kamal Jain, Ion Ma˘ndoiu, Sridhar Rajagopalan, Huzur Saran, and Mihalis Yannakakis – my extensive collaborations with them helped shape many of the ideas presented in this book. I was fortunate to get Ion Ma˘ndoiu’s help and advice on numerous matters–hiseleganteyeforlayoutandfigureshelpedshapethepresentation. A special thanks, Ion! I would like to express my gratitude to numerous experts in the field for generous help on tasks ranging all the way from deciding the contents and itsorganization,providingfeedbackonthewriteup,ensuringcorrectnessand completeness of references to designing exercises and helping list open prob- lems. Thanks to Sanjeev Arora, Alan Frieze, Naveen Garg, Michel Goemans, Mark Jerrum, Claire Kenyon, Samir Khuller, Daniele Micciancio, Yuval Ra- bani, Sridhar Rajagopalan, Dana Randall, Tim Roughgarden, Amin Saberi, Leonard Schulman, Amin Shokrollahi, and Mihalis Yannakakis, with special thanks to Kamal Jain, E´va Tardos, and Luca Trevisan. Numerous other people helped with valuable comments and discussions. Inparticular,IwouldliketothankSarmadAbbasi,CristinaBazgan,Rogerio BritoGruiaCalinescu,AmitChakrabarti,MossesCharikar,JosephCheriyan, VasekChv´atal,UriFeige,CristinaFernandes,AshishGoel,ParikshitGopalan, Mike Grigoriadis, Sudipto Guha, Dorit Hochbaum, Howard Karloff, Leonid Khachian, Stavros Kolliopoulos, Jan van Leeuwen, Nati Lenial, George Leuker, Vangelis Markakis, Aranyak Mehta, Rajeev Motwani, Prabhakar Raghavan, Satish Rao, Miklos Santha, Jiri Sgall, David Shmoys, Alistair Sinclair, Prasad Tetali, Pete Veinott, Ramarathnam Venkatesan, Nisheeth Vishnoi, and David Williamson. I am sure I am missing several names – my apologies and thanks to these people as well. A special role was played by the numerous students who took my courses on this topic and scribed notes. It will be impossible to individually remember their names. I would like to express my gratitude collectively to them. IwouldliketothankIITDelhi–withspecialthankstoShachinMahesh- wari – Georgia Tech, and DIMACS for providing pleasant, supportive and academically rich environments. Thanks to NSF for support under grants CCR-9627308 and CCR-9820896. Preface XI It was a pleasure to work with Hans Wo¨ssner on editorial matters. The personal care with which he handled all such matters and his sensitivity to an author’s unique point of view were especially impressive. Thanks also to Frank Holzwarth for sharing his expertise with LATEX. A project of this magnitude would be hard to pull off without whole- heartedsupportfromfamilymembers.Fortunately,inmycase,someofthem are also fellow researchers – my wife, Milena Mihail, and my brother, Umesh Vazirani. Little Michel’s arrival, halfway through this project, brought new joys and energies, though made the end even more challenging! Above all, I would like to thank my parents for their unwavering support and inspira- tion – my father, a distinguished author of several Civil Engineering books, andmymother,withherdeepunderstandingofIndianClassicalMusic.This book is dedicated to them. Atlanta, Georgia, May 2001 Vijay Vazirani