A 40-page sketch of basic techniques in the design and
analysis of combinatorial approximation algorithms.
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.