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.

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.
Fundamentals of Computation Theory
INTERNATIONAL CONFERENCE ON FUNDAMENTALS OF COMPUTATION THEORY
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 identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2158/237685
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact