Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-084 | 1st October 2001 00:00

When does a dynamic programming formulation guarantee the existence of an FPTAS?

RSS-Feed




TR01-084
Authors: Gerhard J. Woeginger
Publication: 27th November 2001 15:33
Downloads: 1121
Keywords: 


Abstract:

We derive results of the following flavor:
If a combinatorial optimization problem can be formulated via a dynamic
program of a certain structure and if the involved cost and transition
functions satisfy certain arithmetical and structural conditions, then
the optimization problem automatically possesses a fully polynomial time
approximation scheme (FPTAS).

Our characterizations provide a natural and uniform approach to fully
polynomial time approximation schemes.
We illustrate their strength and generality by deducing from them the
existence of FPTASs for a multitude of scheduling problems.
Many known approximability results follow as corollaries from
our main result.



ISSN 1433-8092 | Imprint