1
$\begingroup$

Suppose you have a Knapsack (optimisation) problem with integer values and weights, and you know the optimal value $OPT$. Can you compute an optimal solution in polynomial time by using a PTAS or FPTAS and setting $\epsilon < 1/OPT$, since this would mean it computes a solution in polynomial time which is of value $\geq (1-\epsilon) OPT > OPT - 1$ which due to values being integers, means it must be an optimal solution?

Also, does this idea generalise by setting $\epsilon$ to something so that $\epsilon OPT$ is smaller than the smallest difference in value between items? This can even be done without knowledge of $OPT$ by searching for the smallest difference $d$ in time $O(n^2)$ for $n$ items and then setting $\epsilon < d / V$ with $V$ being the sum of all item values.

Is there perhaps a catch about Knapsack being a weakly NP-hard problem, meaning $OPT$ isn't a value bounded polynomially by the input size (even if $OPT$ is given, since it's given in binary) and thus the runtime of the PTAS or FPTAS isn't polynomial...?

$\endgroup$

1 Answer 1

1
$\begingroup$

The runtime of a FPTAS is polynomial in the input size and in $1/\epsilon$. However, if $\epsilon$ depends on parameters which may not be polynomial in the input size, such as in this case $OPT$ or $V$, then the algorithm is not a polynomial time algorithm.

It is however a pseudo-polynomial time algorithm, since the running time is polynomial in the value of the input, if not in the size of the input. But at this point, it is a better idea to directly use the pseudo-polynomial time dynamic algorithm for Knapsack (since this is the underlying mechanism for the FPTAS anyway).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.