The question is: Does a poly-time approximation scheme always exist for NP-complete problems that have pseudo-polynomial time algorithms (like knapsack for example)?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
The short answer is NO. Petra Schuurman and Gerhard Woeginger have written about this in their tutorial. See Example 0.6.3 on p.46 in their paper when there's no FPTAS while problem has pseudopolynomial algorithm. What concerns an example when there's no PTAS while problem has pseudopolynomial algorithm I suggest Binary Paint Shop Problem (discussed also here, definition can be found in the first answer).
Also there is good picture in tutorial on p.5 on relations between approximation classes and Pseudo-Polynomial Time.
answered Mar 15, 2011 at 18:59
$\begingroup$
$\endgroup$
It depends. Gerhard Woeginger has a paper on a related problem: when a dynamic programming formulation of a problem leads to a PTAS.
answered Mar 15, 2011 at 16:40
$\begingroup$
$\endgroup$
You should look at Sect. 2.4. of Giorgio Ausiello, Pierluigi Crescenzi, Marco Protasi: Approximate Solution of NP Optimization Problems. Theor. Comput. Sci. 150(1): 1-55 (1995).
They prove how pseudo-polynomial algorithms and FPTASs (that is PTASs whose time complexity is polynomial in $1/\epsilon$) are related.
answered Mar 16, 2011 at 9:23