8
$\begingroup$

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)?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

It depends. Gerhard Woeginger has a paper on a related problem: when a dynamic programming formulation of a problem leads to a PTAS.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy