Table of contents
-
The complexity of optimization problems
- Analysis of algorithms and complexity of problems
- Complexity classes of decision problems
- Reducibility among problems
- Complexity of optimization problems
-
Design techniques for approximation algorithms
- The greedy method
- Sequential algorithms for partitioning problems
- Local search
- Linear programming based algorithms
- Dynamic programming
- Randomized algorithms
- Approaches to the approximate solution of problems
-
Approximation classes
- Approximate solutions with guaranteed performance
- Polynomial-time approximation schemes
- Fully polynomial-time approximation schemes
-
Input-dependent and asymptotic approximation
- Between APX and NPO
- Between APX and PTAS
-
Approximation through randomization
- Randomized algorithms for weighted vertex cover
- Randomized algorithms for weighted satisfiability
- Algorithms based on semidefinite programming
- The method of the conditional probabilities
-
NP, PCP and non-approximability results
- Formal complexity theory
- Oracles
- The PCP model
- Using PCP to prove non-approximability results
-
The PCP theorem
- Transparent long proofs
- Almost transparent short proofs
- The final proof
-
Approximation preserving reductions
- The world of NPO problems
- AP-reducibility
- NPO-completeness
- APX-completeness
- Other APX-complete problems
-
Probabilistic analysis of approximation algorithms
- Introduction
- Techniques for the probabilistic analysis of algorithms
- Probabilistic analysis and multiprocessor scheduling
- Probabilistic analysis and bin packing
- Probabilistic analysis and maximum clique
- Probabilistic analysis and graph coloring
- Probabilistic analysis and Euclidean TSP
-
Heuristic methods
- Types of heuristics
- Construction heuristics
- Local search heuristics
- Heuristics based on local search
All chapters also contain a section Excercises and a section Bibliographical notes.
Appendix
-
Mathematical preliminaries
-
A list of NP optimization problems
Last modified November 1999
Viggo Kann
<viggo@nada.kth.se>