ABSTRACT
In this chapter we introduce the so-called differential approximation ratio as a measure of the quality of the solutions obtained by approximation algorithms. After providing motivations and basic definitions we 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. Finally, we discuss some structural results concerning approximation classes based on the differential ratio. Throughout the chapter we make use of the notations introduced in Chapter 15. Also, given an approximation algorithm A for an NP optimization problem (the class of these problems is called NPO), we denote by mA(x , y), the value of the solution y computed by A on instance x of . When clear from the context, reference to A will be omitted. The definitions of most of the problems dealt in this chapter can be found in Refs. [1,2]; also, for graph-theoretic notions, interested readers are referred to Ref. [3].
