Design and Analysis of Approximation Algorithms

• Κύριοι συγγραφείς: Du, Ding-Zhu (Συγγραφέας), Ko, Ker-I (Συγγραφέας), Hu, Xiaodong (Συγγραφέας)
• Συγγραφή απο Οργανισμό/Αρχή: SpringerLink (Online service)
• Μορφή: Ηλεκτρονική πηγή Ηλ. βιβλίο
• Γλώσσα: English
• Έκδοση: New York, NY : Springer New York, 2012.
• Σειρά: Springer Optimization and Its Applications, 62
• Θέματα: Mathematics.; Algorithms.; Mathematical optimization.; Optimization.; Algorithm Analysis and Problem Complexity.

When precise algorithmic solutions are difficult to compute, the use of approximation algorithms can help. Design and Analysis of Approximation Algorithms is a textbook for a graduate course in theoretical computer science taught globally in universities. It can also be used as a reference work for...

Πίνακας περιεχομένων:

• Preface
• 1. Introduction
• 2. Greedy Strategy
• 3. Restriction
• 4. Partition
• 5. Guillotine Cut
• 6. Relaxation
• 7. Linear Programming
• 8. Primal-Dual Scheme and Local Ratio
• 9. Semidefinite Programming
• 10. Inapproximability
• Bibliography
• Index.