Approximation Algorithms.pdf

【实例简介】
Approximation Algorithms.pdf，Vijay V. Vazirani auth， Spring 出版社的近似算法经典教材
Vijay V. vazirani Approximation algorithms S》 Springer Vijay v, vazirani Georgia Institute of Technology College of Computing 801 Atlantic avenue Atlanta, GA 30332-028o USA vazirani@cc.gatech.edu http://www.cc.gatech.edu/facvijayvazirani Corrected Second Printing 2003 Library of Congress Cataloging-in-Publication Data Vazirani, vijay V. Approximation algorithms/Vijay V Vazirani Includes bibliographical references and index. ISBN9783-642-084690 ISBN983-662-04565-7( eBook) DOIo1oo7/978-3-66204565-7 1. Computer algorithms. 2. Mathematical optimization. I. Title. QA76.9A43V3920 0o5-1-dc21 ACM Computing Classification(1998): F1-2, G1.2, G 1.6, G2-4 AMS Mathematics Classification(2000): 68-01; 68W05, 20, 25, 35, 40 68005-17,25;68R05,10;90-08;90C05,08,10,22,27,35,46,47,59,90; 05A05;05C05,12,20,38,40,45,6970,85,90;11H06;15A03,15,18,39,48 ISBN9783642-084690 his work is subject to copyright. All rights are reserved, whether the whole or part of the material concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broad casting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag Berlin Heidelberg gmbH Violations are liable for prosecution under the German Copyright Law. http://www.springer.de O Springer-Verlag Berlin Heidelberg 2001,2003 Originally published by Springer-Verlag Berlin Heidelberg New York in 2003 oftcover reprint of the hardcover ist edition 2003 The use of general descriptive names, registered names, trademarks, etc in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover Design: KunkelLopka, Heidelberg Typesetting: Camera-ready by the author using a Springer TEX macro package Printed on acid-free paper SPIN 10889341 45/3142X0-543210 o my parents Preface Although this may seem a parador, all science is dominated by the idea of approximation Be 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 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 This book is divided into three parts. In Part I we cover 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 Il, 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 discovering good relaxations, just as there is no fixed 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 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 opti- mization, problems(counting the number of solutions to a given instance) The counting versions of almost all known NP-complete problems are #P complete. 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- taining efficient approximate counting algorithms for this latter class of prob VIII Preface 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 approximation algorithms, but also in this book. It offers 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 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- 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 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 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 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 relegated to exercises. The exercises also cover other important results which could not be covered in detail due to logistic constraints. Hints have been 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 Preface IX 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 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 Appendix B, linear programming in Chapter 12, semidefinite 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 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 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 lon Mandoiu. 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 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 needs to be fine tuned to the types of instances arising in specific applications We hope that this book will serve as a catalyst in helping this theory grow and have practical impact X Pl reface 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 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 Mandoiu 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 Mandoiu's help and advice on numerous matters-his elegant eye for layout and figures helped shape the presentation 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 its organization, providing feed back 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, Roge- rio Brito, Gruia Calinescu, Amit Chakrabarti, Mosses Charikar, Joseph Cheriyan, Vasek Chvatal, Uri Feige, Cristina Fernandes, Ashish Goel, Parik shit Gopalan, Mike Grigoriadis, Sudipto Guha, Dorit Hochbaum, Howard Karloff, Leonid Khachian, Stavros Kolliopoulos, Jan van Leeuwen, Nati Le- nial, 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 ccr9820896 It was a pleasure to work with Hans Wossner 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 IATEX Preface XI A project of this magnitude would be hard to pull off without whole hearted support from family members. Fortunately, in my case, some of them are also fellow researchers -my wife, Milena Mihail, and my brother, Umesh Vazirani. Little Michels arrival, halfway through this project, brought new joys and energies, though made the end even more challenging! Above all I would like ce to thank my parents for their unwavering support and inspira tion- my father, a distinguished author of several Civil Engineering books and my mother, with her deep understanding of Indian Classical Music. This book is dedicated to them Atlanta, Georgia, May 2001 Vijay vazirani 【实例截图】
【核心代码】