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 $ \rho (n) $, if for any input size $n$, the cost $C$ of the solution produced by the algorithm is within a factor of $ \rho (n) $ of the cost $C*$ of an optimal solution : $ max \left( \frac{C}{C*},\frac{C*}{C} \right) \le \rho(n) $.

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 $ \sigma > 0 $ such that for any fixed $ \sigma $, the scheme is a $ (1 + \sigma) $ approximation algorithm. An approximation scheme is a polynomial time approximation scheme if for any fixed $ \sigma > 0 $, the scheme runs in time polynomial in the size $n$ of its input instance and is a fully polynomial time approximation scheme if its running time is polynomial both in $ \frac{1}{\sigma} $ and in the size $n$ 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 $ \roh(n) $ - 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.