The Design of Approximation Algorithms (Hardcover)

David P. Williamson, David B. Shmoys

  • 出版商: Cambridge
  • 出版日期: 2011-04-26
  • 售價: $2,900
  • 貴賓價: 9.8$2,842
  • 語言: 英文
  • 頁數: 518
  • 裝訂: Hardcover
  • ISBN: 0521195276
  • ISBN-13: 9780521195270
  • 相關分類: Algorithms-data-structures
  • 立即出貨 (庫存 < 3)

買這商品的人也買了...

商品描述

Discrete 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.

商品描述(中文翻譯)

離散優化問題無所不在,從傳統的運籌學計劃問題,如排程、設施選址和網絡設計;到資料庫中的計算機科學問題;再到病毒式營銷中的廣告問題。然而,大多數這類問題都是 NP-hard 的。因此,除非 P = NP,否則沒有有效的算法可以找到這類問題的最優解。本書展示了如何設計近似算法:能夠找到可證明接近最優解的高效算法。本書圍繞著設計近似算法的核心算法技術組織,包括貪婪和局部搜索算法、動態規劃、線性和半定規劃,以及隨機化。本書的第一部分的每一章都專注於一個單一的算法技術,然後應用於幾個不同的問題。第二部分重新討論這些技術,但提供了更複雜的處理方法。本書還介紹了證明優化問題難以近似的方法。本書設計為研究生級別的算法課程教材,也可作為對離散優化問題的啟發性解決方案感興趣的研究人員的參考書。