First Fit (FF) requires 10m bins: Why

  • Thread starter zak100
  • Start date
  • #1
zak100
Gold Member
462
11

Summary:

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

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
.Scott
Homework Helper
2,536
914
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.
 
Last edited:
  • Like
Likes zak100
  • #3
zak100
Gold Member
462
11
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.
 
  • #4
1,955
252
∗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.
 
  • Like
Likes zak100
  • #5
zak100
Gold Member
462
11
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
first fit requiring 10 bin.jpg
 
  • Like
Likes .Scott
  • #6
.Scott
Homework Helper
2,536
914
@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.
 
  • Like
Likes zak100

Related Threads on First Fit (FF) requires 10m bins: Why

Replies
4
Views
214
  • Last Post
Replies
12
Views
1K
  • Last Post
Replies
5
Views
3K
Replies
45
Views
5K
Replies
7
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
1
Views
935
Top