You are here

The Design of Approximation Algorithms

David P. Williamson and David B. Shmoys
Publisher: 
Cambridge University Press
Publication Date: 
2011
Number of Pages: 
504
Format: 
Hardcover
Price: 
55.00
ISBN: 
9780521195270
Category: 
Textbook
We do not plan to review this book.

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.