<p>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.</p>

CC BY-SA 3.0
2012-04-26T20:56:35.413Z
2012-04-26T20:56:35.413Z
user8477
<p>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.</p>

<p>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}$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-22T16:26:52.930Z
The answer to the _title_ is "No."
Jeffε
CC BY-SA 3.0
2012-04-26T14:53:42.967Z
You'll probably need to define a probability distribution for the $w_i$ and for $W$.
Yuval Filmus
CC BY-SA 3.0
2013-01-25T05:04:55.427Z
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
CC BY-SA 4.0
2021-05-28T18:55:59.930Z
Here's a closely related greedy 2-approximation algorithm: https://cstheory.stackexchange.com/a/49034/8237
Neal Young
<cc.complexity-theory><optimization><time-complexity>
Optimality of Greedy algorithm for minimization Knapsack Problem
Richard
# Optimality of Greedy algorithm for minimization Knapsack Problem

(Asked by: username_0 on 2012-04-21)

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.

**Tags:** cc.complexity-theory, optimization, time-complexity
> **Comments:**
> **username_1**: The answer to the _title_ is "No."  
> **username_2**: You'll probably need to define a probability distribution for the $w_i$ and for $W$.  
> **username_3**: 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.  
> **username_3**: Here's a closely related greedy 2-approximation algorithm: https://cstheory.stackexchange.com/a/49034/8237  

---

## 1 answers

### Answer by username_4 on 2012-04-26. Score: -1

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.


---

