On polynomial time approximation schemes and approximation preserving reductions

摘要

We show that a fully polynomial time approximation scheme given for an optimization problem can always be simply modified to a polynomial time algorithm solving the problem optimally if the computation model is the deterministic Turing Machine or the logarithmic cost RAM and if the range of the error bound is the rational numbers or a subset (0,b). Moreover, we prove that a P-reduction is not necessarily an A-reduction for some suitable error bound transformation but we give a sufficient criteria.