ABSTRACT
Restriction is one of the most basic techniques to design approximation algorithms. The idea is to generate a solution to a given problem P https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_798.tif"/> by providing an optimal or suboptimal solution to a subproblem of P https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_799.tif"/> . A subproblem of a problem P https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_800.tif"/> means restricting the solution space for P https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_801.tif"/> by disallowing a subset of the feasible solutions. Restriction may be structural or algorithmic. In the case of structural restriction, the idea is to impose some structure on the set of feasible solutions (the solution space), which can be exploited by an efficient algorithm that solves the problem optimally or suboptimally. In the case of algorithmic restriction, an algorithm restricts the set of feasible solutions that may be found. The problem in the restricted solution spaces is referred as the subproblem. For this approach to be effective the subproblem must have the property that for every problem instance, its optimal or suboptimal solution should have an objective function value that is “close” to the optimal one for the original problem. The most common approach is to solve the subproblem once but there are algorithms where more than one subproblem is solved, and then the best of the solutions computed is the solution generated. In this chapter we discuss this methodology and show how to apply it to several problems. Approximation algorithms based on this approach are discussed in Volume 1, Chapters 31, 32, 36, and Volume 2, Chapters 6 and 15.
