We introduce a formal framework for studying approximation properties of NP optimization (NPO) problems. The classes of approximable problems we consider are those appearing in the literature, namely the class of approximable problems within a constant ε (APX), and the class of problems having a polynomial time approximation scheme (PTAS). We define natural approximation preserving reductions and obtain completeness results in NPO, APX, and PTAS. A complete problem in a class cannot have stronger approximation properties unless P = NP. We also show that the degree structure of NPO allows intermediate degrees, that is, if P ≠ NP, there are problems which are neither complete nor belong to a lower class.

COMPLETENESS IN APPROXIMATION CLASSES / P. CRESCENZI; A. PANCONESI. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - STAMPA. - 93:(1991), pp. 241-262. [10.1016/0890-5401(91)90025-W]

COMPLETENESS IN APPROXIMATION CLASSES

CRESCENZI, PIERLUIGI;
1991

Abstract

We introduce a formal framework for studying approximation properties of NP optimization (NPO) problems. The classes of approximable problems we consider are those appearing in the literature, namely the class of approximable problems within a constant ε (APX), and the class of problems having a polynomial time approximation scheme (PTAS). We define natural approximation preserving reductions and obtain completeness results in NPO, APX, and PTAS. A complete problem in a class cannot have stronger approximation properties unless P = NP. We also show that the degree structure of NPO allows intermediate degrees, that is, if P ≠ NP, there are problems which are neither complete nor belong to a lower class.
1991
93
241
262
P. CRESCENZI; A. PANCONESI
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/205976
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 66
  • ???jsp.display-item.citation.isi??? 47
social impact