neal young / Klein99Approximation
A 40-page sketch of basic techniques in the design and analysis of combinatorial approximation algorithms. Sections: Introduction, Underlying principles, Approximation algorithms with small additive error, Performance guarantees, Randomized rounding and linear programming, Performance ratios and c-approximation, Polynomial approximation schemes, Constant-factor performance guarantees, Logarithmic performance guarantees, Multi-criteria problems, Hard-to-approximate problems, Research Issues and Summary, Defining Terms, Further Information.
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.