ABSTRACT
This chapter introduces the so-called differential approximation ratio as measure of the quality of the solutions obtained by approximation algorithms. After providing motivations and basic definitions show examples of optimization problems for which the evaluation of approximation algorithms based on the differential ratio appears to be more meaningful than the usual approximation ratio used in the classical approach to approximation algorithms. In general, no systematic way allows to link results obtained in standard and differential approximation paradigms when dealing with minimization problems. In other words, there is no evident transfer of positive or inapproximability results from one framework to the other one. Min coloring has been systematically studied in the differential paradigm. In any approximation paradigm, the notion of asymptotic approximation is pertinent. In the standard paradigm, the asymptotic approximation ratio is defined on the hypothesis that the interesting instances of the simple problems are the ones whose values of the optimum solutions tend to 8.
