In this paper we generalize the notion of polynomial-time approximation scheme preserving reducibility, called PTAS-reducibility. As a first application of this generalization, we prove the APX-completeness of a polynomially bounded optimization problem, that is, an APX problem whose measure function is bounded by a polynomial in the length of the instance and such that any APX problem is reducible to it. As far as we know, no such problem was known before. This result has been recently used to show that several natural optimization problem are APX-complete, such as max cut, max sat, min node cover, and min δ-TSP. Successively, we apply the notion of APX-completeness to the study of the relative complexity of evaluating an ε-approximate value and computing an ε-approximate solution for any ε. We first show that if P ≠ NP ∩ coNP then the former question can be easier than the latter even if the optimization problem is NP-hard. We therefore give strong evidence that if an optimization problem is APX-complete then the two questions are both hard.

ON APPROXIMATION SCHEME PRESERVING REDUCIBILITY AND ITS APPLICATIONS / P. CRESCENZI; L. TREVISAN. - STAMPA. - (1994), pp. 330-341. ((Intervento presentato al convegno FOURTEENTH CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE.

ON APPROXIMATION SCHEME PRESERVING REDUCIBILITY AND ITS APPLICATIONS

CRESCENZI, PIERLUIGI;
1994

Abstract

In this paper we generalize the notion of polynomial-time approximation scheme preserving reducibility, called PTAS-reducibility. As a first application of this generalization, we prove the APX-completeness of a polynomially bounded optimization problem, that is, an APX problem whose measure function is bounded by a polynomial in the length of the instance and such that any APX problem is reducible to it. As far as we know, no such problem was known before. This result has been recently used to show that several natural optimization problem are APX-complete, such as max cut, max sat, min node cover, and min δ-TSP. Successively, we apply the notion of APX-completeness to the study of the relative complexity of evaluating an ε-approximate value and computing an ε-approximate solution for any ε. We first show that if P ≠ NP ∩ coNP then the former question can be easier than the latter even if the optimization problem is NP-hard. We therefore give strong evidence that if an optimization problem is APX-complete then the two questions are both hard.
Foundation of Software Technology and Theoretical Computer Science
FOURTEENTH CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
P. CRESCENZI; L. TREVISAN
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/237690
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact