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.