The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking. In this paper we obtain new results on the structure of several computationally-defined approximation classes. In particular, after defining a new approximation preserving reducibility to be used for as many approximation classes as possible, we give the first examples of natural NPO-complete problems and the first examples of natural APX-intermediate problems. Moreover, we state new connections between the approximability properties and the query complexity of NPO problems.
STRUCTURE IN APPROXIMATION CLASSES / P. CRESCENZI; V. KANN; R. SILVESTRI; L. TREVISAN. - STAMPA. - (1995), pp. 539-548. (Intervento presentato al convegno FIRST ANNUAL INTERNATIONAL CONFERENCE ON COMPUTING AND COMBINATORICS) [10.1007/BFb0030875].
STRUCTURE IN APPROXIMATION CLASSES
CRESCENZI, PIERLUIGI;
1995
Abstract
The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking. In this paper we obtain new results on the structure of several computationally-defined approximation classes. In particular, after defining a new approximation preserving reducibility to be used for as many approximation classes as possible, we give the first examples of natural NPO-complete problems and the first examples of natural APX-intermediate problems. Moreover, we state new connections between the approximability properties and the query complexity of NPO problems.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
