2
$\begingroup$

In all the presentations of an FPTAS for Knapsack I've seen, it is asserted that the optimal value is at always at least the value of the maximum-valued item (e.g. here, slide 12, where we have $V \leq V^*$, where $V$ is the value of the maximum valued item and $V^*$ is the optimal solution.).

Why is that? I mean, we could have a knaspack problem with two items, one with value $10000$ and size $10000$, and one with value $1$ and size $1$, and for a knapsack capacity of $1$ clearly the optimal solution is $1$, but $V = 10000$, and $V^* < V$.

$\endgroup$
3
$\begingroup$

It is common to assume without loss of generality that the maximum item weight is at most as large as the knapsack capacity. That is okay (in the context of complexity theory) because filtering out items that are too large to fit even alone is easily possible in a polynomial-time preprocessing step.

If the sources do not mention that they are sloppy.

And in that case, every item fits into the knapsack alone, hence you can obtain the maximum item value with a trivial singleton solution.

Nota bene: As soon as we are talking algorithms and want to derive running times, such assumptions are not necessarily w.l.o.g. In case the running time cost of the preprocessing is dominant we should not lie it away.

$\endgroup$

Your Answer

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

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