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.
A SHORT GUIDE TO APPROXIMATION PRESERVING REDUCTIONS / P. CRESCENZI. - STAMPA. - (1997), pp. 262-273. (Intervento presentato al convegno TWELFTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY) [10.1109/CCC.1997.612321].
A SHORT GUIDE TO APPROXIMATION PRESERVING REDUCTIONS
CRESCENZI, PIERLUIGI
1997
Abstract
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.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
