Table of contents

  1. The complexity of optimization problems
    1. Analysis of algorithms and complexity of problems
    2. Complexity classes of decision problems
    3. Reducibility among problems
    4. Complexity of optimization problems

  2. Design techniques for approximation algorithms
    1. The greedy method
    2. Sequential algorithms for partitioning problems
    3. Local search
    4. Linear programming based algorithms
    5. Dynamic programming
    6. Randomized algorithms
    7. Approaches to the approximate solution of problems

  3. Approximation classes
    1. Approximate solutions with guaranteed performance
    2. Polynomial-time approximation schemes
    3. Fully polynomial-time approximation schemes

  4. Input-dependent and asymptotic approximation
    1. Between APX and NPO
    2. Between APX and PTAS

  5. Approximation through randomization
    1. Randomized algorithms for weighted vertex cover
    2. Randomized algorithms for weighted satisfiability
    3. Algorithms based on semidefinite programming
    4. The method of the conditional probabilities

  6. NP, PCP and non-approximability results
    1. Formal complexity theory
    2. Oracles
    3. The PCP model
    4. Using PCP to prove non-approximability results

  7. The PCP theorem
    1. Transparent long proofs
    2. Almost transparent short proofs
    3. The final proof

  8. Approximation preserving reductions
    1. The world of NPO problems
    2. AP-reducibility
    3. NPO-completeness
    4. APX-completeness
    5. Other APX-complete problems

  9. Probabilistic analysis of approximation algorithms
    1. Introduction
    2. Techniques for the probabilistic analysis of algorithms
    3. Probabilistic analysis and multiprocessor scheduling
    4. Probabilistic analysis and bin packing
    5. Probabilistic analysis and maximum clique
    6. Probabilistic analysis and graph coloring
    7. Probabilistic analysis and Euclidean TSP

  10. Heuristic methods
    1. Types of heuristics
    2. Construction heuristics
    3. Local search heuristics
    4. Heuristics based on local search
All chapters also contain a section Excercises and a section Bibliographical notes.

Appendix
  1. Mathematical preliminaries
  2. A list of NP optimization problems
Last modified November 1999
Viggo Kann <viggo@nada.kth.se>