Design and Analysis of Approximation Algorithms

• Main Authors: Du, Ding-Zhu (Author), Ko, Ker-I (Author), Hu, Xiaodong (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: New York, NY : Springer New York, 2012.
• Series: Springer Optimization and Its Applications, 62
• Subjects: 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...

Table of Contents:

• 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.