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.