# Optimality of Greedy algorithm for minimization Knapsack Problem

Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized.

The greedy algorithm simply sorts items based on ratio $\frac{p_i}{w_i}$. It scans and sum up the sorted items in increasing order, until $\sum{w_i}\geq{W}$. Then outputs $\sum{p_i}$.

If the distribution of $p_i$ is known (say, following zipf distribution) and $w_i$ is randomly distributed, and independently with value of $p_i$, then what is the average optimality ratio which is ratio of $\sum_{i\in{I}}{p_i}$ to the optimal results.

Note: in worst case, this greedy algorithm can be arbitrarily bad, according to following book. P412, Knapsack Problems, By Hans Kellerer, Ulrich Pferschy, David Pisinger.

• The answer to the title is "No." – Jeffε Apr 22 '12 at 16:26
• You'll probably need to define a probability distribution for the $w_i$ and for $W$. – Yuval Filmus Apr 26 '12 at 14:53
• A trivial observation that may give some intuition is that the fractional greedy algorithm gives you a lower bound on OPT. (Fractional greedy differs from greedy only in that it takes a fractional amount of the last item, just enough to make the sum of the weights equal to $W$.) As a consequence, for the regular greedy algorithm, the profit of the items taken minus the last is a lower bound on OPT. So, if your distribution is such that the last item take by greedy has relatively small profit (e.g. items profits are "small" relative to the total), then greedy will be close to OPT. – Neal Young Jan 25 '13 at 5:04