Approximability preserving reductions (septembre 2005)
Giorgio Ausiello, Vangélis Th. Paschos · HAL (Le Centre pour la Communication Scientifique Directe) · 2005
We present in this paper a tour d'horizon of the most important approximation-preserving reductions that have strongly influenced research about structure in approximability classes. Preliminary version of Chapter 7 to appear in T. Gongalez (ed.), Approximation algorithms and metaheuristics, Taylor and Francis.