ECCC-Report TR96-043https://eccc.weizmann.ac.il/report/1996/043Comments and Revisions published for TR96-043en-usThu, 22 Aug 1996 16:34:44 +0300
Paper TR96-043
| On polynomial time approximation schemes and approximation preserving reductions |
Edmund Ihler
https://eccc.weizmann.ac.il/report/1996/043We 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.
Thu, 22 Aug 1996 16:34:44 +0300https://eccc.weizmann.ac.il/report/1996/043