• Menu
  • Skip to right header navigation
  • Skip to main content
  • Skip to secondary navigation
  • Skip to primary sidebar

OnlineProgrammingBooks.com

Legally Free Computer Books

  • All Categories
  • All Books
  • All Categories
  • All Books
  • About Us
  • Privacy policy
  • Disclaimer
  • Subscribe
  • Contact
You are here: Home ▶ Algorithms & Data Structures ▶ The Design of Approximation Algorithms

The Design of Approximation Algorithms

February 9, 2011

Free eBook: The Design of Approximation Algorithms

Free eBook “The Design of Approximation Algorithms” by David P. Williamson and David B. Shmoys. The book is organized around several central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization.

Book Description

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 who are interested in the heuristic solution of discrete optimization problems.

Table of Contents

  • An introduction to approximation algorithms
  • Greedy algorithms and local search
  • Rounding data and dynamic programming
  • Deterministic rounding of linear programs
  • Random sampling and randomized rounding of linear programs
  • Randomized rounding of semidefinite programs
  • The primal-dual method
  • Cuts and metrics
  • Further uses of greedy and local search algorithms
  • Further uses of rounding data and dynamic programming
  • Further uses of deterministic rounding of linear programs
  • Further uses of random sampling and randomized rounding of linear programs
  • Further uses of randomized rounding of semidefinite programs
  • Further uses of the primal-dual method
  • Further uses of cuts and metrics
  • Techniques in proving the hardness of approximation
  • Open Problems

Download Free PDF / Read Online

Author(s): David P. Williamson and David B. Shmoys.
Format(s): PDF
File size: 2.28 MB
Number of pages: 500
Link: Download.

Similar Books:

  1. Greedy Algorithms
  2. Problems on Algorithms
  3. Algorithms: Fundamental Techniques
  4. Advances in Evolutionary Algorithms
  5. Dictionary of Algorithms and Data Structures
Previous Post: « Scala By Example
Next Post: Microsoft Office Powerpoint »

Primary Sidebar

Get Latest Updates

  • Facebook
  • Pinterest
  • RSS
  • Twitter
  • YouTube
  • About Us
  • Privacy policy
  • Disclaimer
  • Subscribe
  • Contact

Copyright © 2006–2025 OnlineProgrammingBooks.com