ICS 269, Winter 1999: Theory Seminar
12 March 1999:
When does a dynamic programming formulation guarantee the existence
of an FPTAS? (SODA99) by G. Woeginger
Speaker: Joseph Wang, ICS, UC Irvine
We derive results of the following flavor: If a combinatorial
optimization problem can be formulated via a dynamic program of
certain structure and if the involved cost and transition functions
satisfy certain arithmetical 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.