近似算法-Vazirani.pdf-资料库

saton_echo-7053543-4744302542902581058.pdf-第1页.png

第1页 / 共396页

saton_echo-7053543-4744302542902581058.pdf-第2页.png

第2页 / 共396页

saton_echo-7053543-4744302542902581058.pdf-第3页.png

第3页 / 共396页

saton_echo-7053543-4744302542902581058.pdf-第4页.png

第4页 / 共396页

saton_echo-7053543-4744302542902581058.pdf-第5页.png

第5页 / 共396页

saton_echo-7053543-4744302542902581058.pdf-第6页.png

第6页 / 共396页

saton_echo-7053543-4744302542902581058.pdf-第7页.png

第7页 / 共396页

saton_echo-7053543-4744302542902581058.pdf-第8页.png

第8页 / 共396页

Vijay V. Vazirani College of Computing Georgia Institute of Technology

Copyright c 2001 Approximation Algorithms Springer Berlin Heidelberg NewYork Barcelona Hong Kong 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 = NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientiﬁc 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 have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms 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 speciﬁc LP-relaxation used, and there is no ﬁxed recipe for discovering good relaxations, just as there is no ﬁxed recipe for proving a the- orem in mathematics (readers familiar with complexity theory will recognize this as the philosophical point behind the P = NP question). Part III covers four important topics. The ﬁrst is the problem of ﬁnding 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 eﬀect yet.

VIII Preface taining eﬃcient approximate counting algorithms for this latter class of prob- 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 ﬁeld. 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 approximation algorithms, but also in this book. It oﬀers a particularly simple setting for introducing key concepts as well as some of the basic algorithm design techniques of Part I and Part II. In order to give a complete treatment 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 diﬃcult 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 eﬀort involved looking for interesting pieces of stone in the quarry and staring at them for long hours to determine the form they natu- rally wanted to take. The chisel work exposed, in a minimalistic manner, this form. By analogy, we would like to start with a clean, simply stated problem (perhaps a simpliﬁed version of the problem we actually want to solve in practice). Most of the algorithm design eﬀort actually goes into understand- ing the algorithmically relevant combinatorial structure of the problem. The algorithm exploits this structure in a minimalistic manner. The exposition of algorithms in this book will also follow this analogy, with emphasis on stating the structure oﬀered 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 relegated to exercises. The exercises also cover other important results which 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 diﬃculty of an exercise and whether a hint is provided for it. This book is suitable for use in advanced undergraduate and graduate level courses on approximation algorithms. It has more than twice the material that can be covered in a semester long course, thereby leaving plenty of room for an instructor to choose topics. An undergraduate course in algorithms and the theory of NP-completeness should suﬃce 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 Appendix B, linear programming in Chapter 12, semideﬁnite programming in Chapter 26, and lattices in Chapter 27. (A disproportionate amount of space 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 ﬁrst 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 diﬃculty. In anticipation of this wide audience, we decided not to publish this book 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 M˘andoiu. Corrections and comments from readers are welcome. We have set up a special email address for this purpose: approx@cc.gatech.edu. 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(log n), of the optimal? Further, by this token, what is the usefulness of improving the approximation guarantee from, say, factor 2 to 3/2? Let us address both issues and point out some fallacies in these assertions. The approximation guarantee only reﬂects 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 diﬃculty 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 conﬁrmed 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 needs to be ﬁne tuned to the types of instances arising in speciﬁc applications.

X Preface We hope that this book will serve as a catalyst in helping this theory grow and have practical impact. Acknowledgments This book is based on courses taught at the Indian Institute of Technology, Delhi in Spring 1992 and Spring 1993, at Georgia Tech in Spring 1997, Spring 1999, and Spring 2000, and at DIMACS in Fall 1998. The Spring 1992 course resulted in the ﬁrst 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 M˘andoiu, 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 M˘andoiu’s help and advice on numerous matters – his elegant eye for layout and ﬁgures helped shape the presentation. A special thanks, Ion! I would like to express my gratitude to numerous experts in the ﬁeld for generous help on tasks ranging all the way from deciding the contents and its organization, providing feedback on the writeup, ensuring correctness and 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, ´Eva Tardos, and Luca Trevisan. Numerous other people helped with valuable comments and discussions. In particular, I would like to thank Sarmad Abbasi, Cristina Bazgan, Rogerio Brito Gruia Calinescu, Amit Chakrabarti, Mosses Charikar, Joseph Cheriyan, Vasek Chv´atal, Uri Feige, Cristina Fernandes, Ashish Goel, Parikshit Gopalan, Mike Grigoriadis, Sudipto Guha, Dorit Hochbaum, Howard Karloﬀ, 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. I would like to thank IIT Delhi – with special thanks to Shachin Mahesh- 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.

资料库

近似算法-Vazirani.pdf

相关推荐

课程资源

热门标签

最新资料