| 紀錄類型: |
書目-語言資料,印刷品
: 單行本
|
| 作者: |
WilliamsonDavid P., |
| 合作者: |
ShmoysDavid Bernard, |
| 出版地: |
Cambridge |
| 出版者: |
Cambridge University Press; |
| 出版年: |
2011 |
| 面頁冊數: |
xi, 504 p.ill. : 26 cm.; |
| 標題: |
Mathematical optimization. - |
| 標題: |
Approximation theory. - |
| 電子資源: |
http://assets.cambridge.org/97805211/95270/cover/9780521195270.jpg |
| ISBN: |
978-0-521-19527-0bound |
| ISBN: |
0-521-19527-6bound |
| 內容註: |
Machine generated contents note: 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 |