Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 35

The authors defined approximation algorithm as an algorithm that returns near optimal results. An algorithm for a problem is said to have an approximation ratio of , if for any input size , the cost of the solution produced by the algorithm is within a factor of of the cost of an optimal solution : .

An approximation scheme for an optimization problem is an approximation algorithm that takes as input not only an instance of the problem, but a value such that for any fixed , the scheme is a approximation algorithm. An approximation scheme is a polynomial time approximation scheme if for any fixed , the scheme runs in time polynomial in the size of its input instance and is a fully polynomial time approximation scheme if its running time is polynomial both in and in the size of the input instance.

The authors then provide an approximation algorithm for vertex cover problem and prove that it is a polynomial time 2-approximation algorithm.

The authors then provide an approximate algorithm for traveling salesman problem with triangle inequality. The authors also prove a theorem that good approximate tours cannot be found in polynomial time unless P = NP.

The authors then provide greedy approximation algorithm for set cover problem and prove that it is a polynomial time - approximation algorithm.

The author then discuss two techniques for designing approximation algorithms:

1. Randomization
2. Linear Programming

The authors then provide a randomized approximation algorithm for MAX-3 CNF satisfiability. The author then provides an approximation algorithm for minimum weight vertex cover.

The authors then provide an exponential time exact algorithm for subset-sum-problem.

The authors then provide an algorithm to TRIM a list. Then the author provides an approximation algorithm for subset-sum-problem and prove that it is a fully polynomial time approximate scheme for the subset-sum-problem.