P. Crescenzi and L. Trevisan.
On Approximation Scheme Preserving Reducibility and its Applications.
In Proceedings of the 14th Conference on Foundations of Software Technology
and Theoretical Computer Science .
LNCS 880, Springer Verlag, pages 330-341, 1994.
- Abstract
- We prove that a polynomially bounded optimization
problem is APX-complete w.r.t. the PTAS-reducibility
This result has been used by Khanna, Motwani, Sudan and
Vazirani to show that Max 3SAT is APX-complete w.r.t.
the PTAS-reducibility. We also consider the relative
hardness of constructing approximate solution vs.
approximating the optimum value for optimization
problems, and we establish some basic results.