Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
Your counterexample seems correct. So is there any characterization or property of knapsack instances which makes the simple greedy approach optimal in their cases? –  BharatRam Jun 3 '11 at 11:57
1  
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? –  BharatRam Jun 3 '11 at 12:07
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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