ABSTRACT
This chapter discusses several approximation algorithms based on restriction. Restriction is one of the most basic techniques to design approximation algorithms. The idea is to generate a solution to a given problem P by providing an optimal or suboptimal solution to a subproblem of P. A subproblem of a problem P means restricting the solution space for P by disallowing a subset of the feasible solutions. Restriction may be structural or algorithmic. The Steiner tree problem is a classical problem in combinatorial optimization. A closely related approach to restriction is transformation-restriction. The idea is to transform the problem instance to a restricted instance of the same problem. The difference is that the restricted problem instance is not a subproblem of original problem instance as in the case of restriction, but it is a "simpler" problem of the same type.
