000			a
999			_c29601 _d29601
008			190810b xxu||||| |||| 00| 0 eng d
020			_a9780521195270
082			_a518​.5 _bWIL
100			_aWilliamson, David P
245			_aDesign of approximation algorithms
260			_bCambridge University Press _c2011 _aCambridge
300			_axi, 504 p. _bill. _c26 cm
365			_b51.99 _cEUR _d4772.68
504			_aIncludes bibliographical references and indexes.
520			_aDiscrete optimization problems are everywhere, from traditional operations research planning problems, such as scheduling, facility location, and network design; to computer science problems in databases; to advertising issues in viral marketing. Yet most such problems are NP-hard. Thus unless P =​ NP, there are no efficient algorithms to find optimal solutions to such problems. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions. The book is organized around central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization. Each chapter in the first part of the book is devoted to a single algorithmic technique, which is then applied to several different problems. The second part revisits the techniques but offers more sophisticated treatments of them. The book also covers methods for proving that optimization problems are hard to approximate. Designed as a textbook for graduate-level algorithms courses, the book will also serve as a reference for researchers interested in the heuristic solution of discrete optimization problems.
650			_aApproximation theory
650			_a Mathematical optimization
650			_aAlgorithmus
650			_aApproximationstheorie
700			_aShmoys, David Bernard
942			_2ddc _cBK