You are here

The Design of Approximation Algorithms

Publisher: 
Cambridge University Press
Number of Pages: 
504
Price: 
55.00
ISBN: 
9780521195270
Date Received: 
Thursday, June 2, 2011
Reviewable: 
No
Include In BLL Rating: 
No
Reviewer Email Address: 
David P. Williamson and David B. Shmoys
Publication Date: 
2011
Format: 
Hardcover
Category: 
Textbook

Part I. An Introduction to the Techniques: 1. An introduction to approximation algorithms
2. Greedy algorithms and local search
3. Rounding data and dynamic programming
4. Deterministic rounding of linear programs
5. Random sampling and randomized rounding of linear programs
6. Randomized rounding of semidefinite programs
7. The primal-dual method
8. Cuts and metrics
Part II. Further Uses of the Techniques: 9. Further uses of greedy and local search algorithms
10. Further uses of rounding data and dynamic programming
11. Further uses of deterministic rounding of linear programs
12. Further uses of random sampling and randomized rounding of linear programs
13. Further uses of randomized rounding of semidefinite programs
14. Further uses of the primal-dual method
15. Further uses of cuts and metrics
16. Techniques in proving the hardness of approximation
17. Open problems
Appendix A. Linear programming
Appendix B. NP-completeness.

Publish Book: 
Modify Date: 
Wednesday, August 3, 2011

Dummy View - NOT TO BE DELETED