5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ The answer to the title is "No." $\endgroup$
    – Jeffε
    Apr 22 '12 at 16:26
  • 2
    $\begingroup$ You'll probably need to define a probability distribution for the $w_i$ and for $W$. $\endgroup$
    – Yuval Filmus
    Apr 26 '12 at 14:53
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Jan 25 '13 at 5:04
  • $\begingroup$ Here's a closely related greedy 2-approximation algorithm: cstheory.stackexchange.com/a/49034/8237 $\endgroup$
    – Neal Young
    May 28 at 18:55
-1
$\begingroup$

I didn't understand the question very well, but I think you're asking about the ratio of the greedy solution to the optimal solution when the problem instances are taken out of a certain probability distribution. I don't have a theoretic solution to this problem, but if you need the answer for practical reasons, then I think a Monte-Carlo simulation would give reliable results. You can approximate knapsack to the desired precision using the well-known dynamic programming algorithm to obtain an approximate value of the optimal solution and then compare it to the greedy algorithm. You generate a number of random instances, and see where the ratio usually falls. In order to have more reliable estimates, you can establish confidence intervals for the fraction of instances whose greedy/optimal ratio falls within a given interval, etc.

Improve this answer
$\endgroup$

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.