The main technique to obtain such kind of results is called the Gap technique. Basically the Gap technique can be described as follows:
- we will reduce a NP complete problem to our optimization problem such that any positive instance will be transformed into an instance whose optimal value is C and any negative instance will be transformed into an instance whose optimal value is distant from C by a gap G.
This will allow us to prove that several problems are not arbitrary well approximable. For examples, we will be able to show that minimum graph colouring is not approximable, we will be able to show that minimum travelling salesperson is not approximable, and will be able to show that minimum bin packing does not admit an approximation scheme.
Basically these results have been obtained until the end of 80s. At the beginning of 90s, an extremely brilliant theorem has been improved by several researches and this theorem is called PCP theorem.
We will see what this theorem says and how this theorem can be applied to obtain new approximability results. In particular, I will show you the maximum sat ability, which belong to class APS, does not belong to the class PTAS.
