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

Improve this question
$\endgroup$

1 Answer 1

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

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.