0
$\begingroup$

Let us consider the knapsack problem. Given a set $P$ of $n$ items where each item has weight $w_i$ and value $v_i$ for all $i=1,2,\ldots,n$. We have two bins, one has a weight limit of $W$ and the other has a weight limit of $W'=2W$. Assume that we have an optimal algorithm $\texttt{OPT}$ that solves the knapsack problem.

Let $O$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the first bin (that has a weight limit of $W$) and to the set of items $P$. Also, let $O'$ denotes the value of an optimal solution when we apply $\texttt{OPT}$ to the second bin (that has a weight limit of $W'=2W$) and to the same set of items $P$.

Can we compare $O$ and $O'$?

I guessed that $$O'\leq 2O.$$

$\endgroup$
2
$\begingroup$

That guess is obviously wrong. If all items have weight 666 and value 1, then you can fit 3 items into a bin of size 2000, and only one into a bin of size 1000.

If all weights are W < $w_i$ ≤ 2W, then O = 0 and O' = highest value of a single item.

There is very little that you can say except the obvious O ≤ O'. You might have "valuable" items with a total weight ≤ W, and all other items are worthless. Then O' is not or only very little greater than O. Or all items with weight ≤ W might be worthless with some items with weight W < $w_i$ ≤ 2W very valuable, then the ratio O' / O can be arbitrarily large.

$\endgroup$
  • $\begingroup$ Thank you. Can we compare $O$ and $O'$ in general? I mean maybe there exists some constant $c$ such that $O'\leq 2O+c$ or something? $\endgroup$ – Ribz Jun 17 '17 at 15:28

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.