We introduce a formal framework for studying approximation properties of NP optimization (NPO) problems. The classes we consider are those appearing in the literature, namely the class of approximable problems within a constant e (APX), the class of problems having a Polynomial-time Approximation Scheme (PAS) and the class of problems having a Fully Polynomial-time Approximation Scheme (FPAS). We define natural approximation preserving reductions and obtain completeness results for these classes. A complete problem in a class can not have stronger approximation properties unless P=NP. We also show that the degree structure of NPO allows intermediate degrees, that is, there are problems which are neither complete nor belong to a lower class.
COMPLETENESS IN APPROXIMATION CLASSES / P. CRESCENZI; A. PANCONESI. - STAMPA. - (1989), pp. 116-126. (Intervento presentato al convegno INTERNATIONAL CONFERENCE ON FUNDAMENTALS OF COMPUTATION THEORY) [10.1007/3-540-51498-8_11].
COMPLETENESS IN APPROXIMATION CLASSES
CRESCENZI, PIERLUIGI;
1989
Abstract
We introduce a formal framework for studying approximation properties of NP optimization (NPO) problems. The classes we consider are those appearing in the literature, namely the class of approximable problems within a constant e (APX), the class of problems having a Polynomial-time Approximation Scheme (PAS) and the class of problems having a Fully Polynomial-time Approximation Scheme (FPAS). We define natural approximation preserving reductions and obtain completeness results for these classes. A complete problem in a class can not have stronger approximation properties unless P=NP. We also show that the degree structure of NPO allows intermediate degrees, that is, there are problems which are neither complete nor belong to a lower class.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
