ON APPROXIMATION SCHEME PRESERVING REDUCIBILITY AND ITS APPLICATIONS

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.