First Fit (FF) requires 10m bins: Why

[zak100]

TL;DR

Hi,
I am trying to read Algorithm book of Allen Weiss which says that FF requires .

Hi,

I am having problem in understanding the following text of the book:

The input consists of 6m items of size 1/7+ Absolon, followed by 6m items of size 1/3+ Absolon , followed by 6m items of size 1/2 + Absolon. One simple packing places one item of each size in a bin and requires 6m bins.

My solution:

If m = 1 then its possible to have 6 bins.

All1/7 elements would go into 1 bin.

All 6*1/3 items would go into 2 bins

All 6 *1/2 items would go into 3 bins.
Total = 6 bins

It further says:

First fit requires 10m bins.

Why First Fit would require 10 bins? I think First Fit would also require 6 bins.
Somebody please guide me why First Fit would need 10 bins?

Zulfi.

 

[.Scott]

The input consists of 6m items of size 1/7+ Absolon, followed by 6m items of size 1/3+ Absolon , followed by 6m items of size 1/2 + Absolon. One simple packing places one item of each size in a bin and requires 6m bins.

You mean "epsilon", not "absolon".

So, I think this is what it says (but please verify).
Input consists of:
6m items of size $(1/7)+\epsilon$
6m items of size $(1/3)+\epsilon$
6m items of size $(1/2)+\epsilon$

It's unclear how big these bins are, but since one of each fits into a single bin, they have to be at least $((1/7)+(1/3)+(1/2)+3*\epsilon) = ((41/42) + 3*\epsilon)$

Perhaps we should assume that the bins are of size 1. Is there something in the problem statement that states this?

So the problem with you solution is that you are ignoring the $\epsilon$. That $\epsilon$ should be taken as a small but finite value. For example, take $\epsilon = 0.001$ then fill those bins again.

 

[zak100]

Hi,

If we would consider epsilon as 0.001
then

$6 * 1/2 + 0.001$ would be greater than 3. So by this optimal should not require 6 bins. It should be more than 6. So first we have to find why optimal requires 6 bins?

ZUlfi.

 

[willem2]

∗1/2+0.0016∗1/2+0.0016 * 1/2 + 0.001 would be greater than 3. So by this optimal should not require 6 bins. It should be more than 6. So first we have to find why optimal requires 6 bins?

But to find the optimal distribution, you have to consider all distributions of the items. .Scott already gave one
distribution where the items do fit in 6 bins. (1 piece of each size in each bin). The total size of the items is too large to fit in 5 bins, so the optimal packing uses 6 bins.

 

[zak100]

Hi,

Thanks, I am able to understand now.

I did the following calculation:

a ==0.00795

==

1/7+0.00795=0.15075*6 = 0.9045 (1 bin)

½ +0.00795=0.50795= (6 bins)

1/3+.00795 = 0.3333+.00795= 0.34125 (2 can fit in one bin) and 6 will require 3 bin . Therefore 1 + 6 +3= 10bins

 

[.Scott]

@zak100 :
But I would suggest you make: $\epsilon \le \frac{1}{126}$
That way, $(1/2+\epsilon)+(1/3+\epsilon)+(1/7+\epsilon) \le 1$
and the 6-bin solution works.