Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

Question

According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved versions.

Also according to my lecture, an approximation scheme is called "fully polynomial time approximation scheme (FPTAS)", if its run time is polynomial in $1/\epsilon$ and polynomial in the encoding length of the instance (usually, the input size is denoted by $n$, such that the encoding length would be $\log n$).

The algorithm has running time $\mathcal{O}(n\log(n))+\mathcal{O}(n + (1/\epsilon)^2)$. I do agree on this being polynomial in $1/\epsilon$, but how is it polynomial in the encoding length of $n$?

The part $\mathcal{O}(n\log(n))$ of the run time is due to sorting the list of $n$ items. As far as I'm capable of judging this, this is polynomial in $n$, but not polynomial in $\log n$.

Where am I wrong?

Answer 1

The input to 0/1 knapsack is a list of $n$ items each with a weight $w_i$ and value $v_i$ with knapsack size $W$ and maximum value $V$. Thus the input list has size $O(n (\log W + \log V))$.

So $n \log n$ is polynomial in the input.

The problem with the traditional dynamic programming solution of knapsack is not that it is exponential in $n$, but that it is polynomial in $W$ (or $V$), which makes it exponential in $\log W$.