The hardness of approximation: gap location

The author refines the complexity analysis of approximation problems, by relating it to a new parameter called gap location. Many of the results obtained so far for approximations yield satisfactory analysis also with respect to this refined parameter, but some known results (e.g. max-k-colorability, max-3-dimensional matching and max not-all-equal 3sat) fall short of doing so. A second contribution of is in filling the gap in these cases by presenting new reductions. Next, he presents definitions and hardness results of new approximation versions of some NP-complete optimization problems. The problems are: vertex cover, k-edge coloring, set splitting, and a restricted version of feedback vertex set and feedback arc set