ABSTRACT
In this chapter we introduce the so-called differential approximation ratio as 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 14. Also, given an approximation algorithm A for an NPO problem Π https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_8852.tif"/> , we denote by m A ( x , y ) https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_8853.tif"/> , the value of the solution y https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_8854.tif"/> computed by A on instance x https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_8855.tif"/> of Π https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_8856.tif"/> . 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 References 1, 2; also, for graph-theoretic notions, interested readers are referred to Reference 3.
