Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR96-043 | 16th August 1996 00:00

On polynomial time approximation schemes and approximation preserving reductions

RSS-Feed




TR96-043
Authors: Edmund Ihler
Publication: 22nd August 1996 16:34
Downloads: 3228
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint