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
 Polynomialtime approximation schemes
 Fully polynomialtime approximation schemes

Inputdependent 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 nonapproximability results
 Formal complexity theory
 Oracles
 The PCP model
 Using PCP to prove nonapproximability results

The PCP theorem
 Transparent long proofs
 Almost transparent short proofs
 The final proof

Approximation preserving reductions
 The world of NPO problems
 APreducibility
 NPOcompleteness
 APXcompleteness
 Other APXcomplete 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>