A short guide to approximation preserving reductions
Pierluigi Crescenzi · 2002
Comparing the complexity of different combinatorial optimization problems has been an extremely active research area during the last 23 years. This has led to the definition of several approximation preserving reducibilities and to the development of powerful reduction techniques. We first review the main approximation preserving reducibilities that have appeared in the literature and suggest which one of them should be used. Successively, we give some hints on how to prove new non-approximability results by emphasizing the most interesting techniques among the new ones that have been developed in the last few years.