The Design of Approximation Algorithms

ISBN-13: 9780521195270 / Angielski / Twarda / 2011 / 518 str.

David P. Williamson; David B. Shmoys

Opis

Designed as a textbook for graduate courses on algorithms, this book presents efficient algorithms that find provably near-optimal solutions.

Recenzje

"The structure of the book is very interesting and allows a deeper understanding of the techniques presented. The whole book manages to develop a way of analyzing approximation algorithms and of designing approximation algorithms that perform well."
Dana Simian, Mathematical Reviews

Spis treści

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.