Before continuing with negative results, we will extend our definition of approximability by introducing the notion of input-dependent and asymptotic approximation. In particular we will see an approximation algorithm for the minimum graph coloring problem, whose performance ration is bounded by n/log n. We will also give an approximation algorithm for the minimum set cover problem. In this case our performance ratio is still a function, but it is a function going less than the previous one because this function the natural logarithm of n. Finally we will see asymptotic approximation scheme for the minimum edge coloring problem. Notice the difference between these two problems. They seem similar but they are extremely different from an approximation point of view. The graph coloring problem ask to color the note of the graph The edge colouring problem ask to color the edges of the graph As you can see the first is not approximable; while the second is very well approximable.

---