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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.