ABSTRACT
The technique of transforming a problem into another in such a way that the solution of the latter entails, somehow, the solution of the former, is a classical mathematical technique that has found wide application in computer science since the seminal works of Cook and Karp who introduced particular kinds of transformations (called reductions) with the aim of studying the computational complexity of combinatorial decision problems. The first kind of approximation preserving reducibility that want to show is a very natural and simple transformation among problems that consists in two linear mappings, one between the values of the optimum solutions of the two problems and one between the errors of the corresponding approximate solutions: the linear reducibility. This chapter shows that an important role played by reductions also in the field of approximation of hard combinatorial optimization problems.
