The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. Many of the counterexamples seem to rely on a worst case feature where the weights of the elements are huge and comparable to the capacity of the knapsack. Suppose in a given instance, this is not so i.e. weights of all elements are very small compared to the capacity of the knapsack. In this case, will the greedy algorithm perform optimally (or atleast near optimally for practical purposes)? I apologize for such a qualitative description, and am seeking a precise formulation for the question, and a possible solution.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
I don't think this works.
Suppose you have a counterexample to the greedy heuristic, with a knapsack of size $S$ and all elements of density at most $D$ and weight at most $W$. Now add a large number $N$ of objects of weight $W$ and density $1000D$, and consider a knapsack of size $S+NW$. Clearly the $N$ 'dense' objects are included in the optimal solution, and after adding them you're left with an instance of the previous counterexample. By making $N$ large enough, you can ensure that the weights of all objects are arbitrarily small compared to the size of the knapsack.
answered Jun 2, 2011 at 14:30
-
$\begingroup$ Your counterexample seems correct. So is there any characterization or property of knapsack instances which makes the simple greedy approach optimal in their cases? $\endgroup$ Jun 3, 2011 at 11:57
-
2$\begingroup$ Also, the greedy algorithm's performance here seems near optimal here, as the difference between its solution and the optimal is just the difference in its performance in the much smaller counterexample we started out with. Can this be quantified? $\endgroup$ Jun 3, 2011 at 12:07
$\begingroup$
$\endgroup$
As Frederico has already shown, this isn't enough to make the greedy heuristic immune to counterexamples.
It's worth mentioning that there is a simple dynamic programming algorithm for the knapsack problem that can be turned into a polynomial time approximation scheme (PTAS) without much difficulty. This can be found in the book by Papadimtiriou and Steiglitz among other places.
answered Jun 2, 2011 at 21:18