Search Results for “first fit bin packing”

Source: First-fit bin packing

First-fit (FF) is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The first-fit algorithm uses the following heuristic:

It keeps a list of open bins, which is initially empty.
When an item arrives, find the first bin into which the item can fit, if any.
If such a bin is found, the new item is placed inside it.
Otherwise, a new bin is opened and the coming item is placed inside it.

Approximation ratio

First

Fit

first

= Asymptotic ratio at most 2

bin

= Asymptotic ratio at most 1.75

= Asymptotic ratio at most 1.7

w
e
i
g
h
t
(
x
)
:=
x
+
b
o
n
u
s
(
x
)

{\displaystyle weight(x):=x+bonus(x)}

.
The asymptotic approximation ratio follows from two claims:

In the optimal packing, the weight of each bin is at most 17/12;
In the First-Fit packing, the average weight of each bin is at least 5/6 = 10/12.
Therefore, asymptotically, the number of bins in the FF packing must be at most 17/10 * OPT.
For claim 1, it is sufficient to prove that, for any set B with sum at most 1, bonus(B) is at most 5/12. Indeed:

If B has no item larger than 1/2, then it has at most five items larger than 1/6, and the bonus of each of them is at most 1/12;
If B has an item larger than 1/2 but no item in [1/3,1/2], then it has room for at most two items in (1/6,1/3), and the sum of their bonuses is at most (1/2 / 2 - 1/6) = 1/12, so the total bonus is 4/12+1/12=5/12.
If B has an item larger than 1/2 and an item in [1/3,1/2], then it has no more room for items of size larger than 1/6, so the total bonus is again 4/12+1/12 = 5/12.
Therefore, the weight of B is at most 1+5/12 = 17/12.
For claim 2, consider first an FF bin B with a single item.

If sum(B)<1/2, then - by the way FF works - all items processed after B must be larger than 1/2 (otherwise they would have been inserted into B). Therefore, there is at most one FF bin with sum<1/2.
Consider now all other bins B with a single item with sum(B)>1/2. For all these bins, weight(B)>1/2+1/3 = 5/6.
Consider now the FF bins B with two or more items.

If sum(B)<2/3, then - by the way FF works - all items processed after B must be larger than 1/3 (otherwise they would have been inserted into B). Therefore, all following bins with two or more items are larger than 2/3. So there is at most one FF bin with two or more items and sum<2/3.
Consider now all other bins with two or more items and sum>2/3. Denote them by B[1],B[2],...B[k], by the order they are opened. For each i in 1,...,k, we prove that the sum of B[i] plus the bonus of B[i+1] is at least 5/6: sum(B[i])+bonus(B[i+1]) ≥ 5/6. Indeed, if sum(B[i]) ≥ 5/6 then the inequality is trivial. Otherwise, let sum(B[i]) := 1 - x. Note that x is between 1/6 and 2/6, since sum(B[i]) is between 2/3 and 5/6. Since B[i+1] is opened after B[i], B[i+1] contains at least two items, say c1 and c2, that do not fit into B[i], that is: c1,c2 > 1-sum(B[i]) = x > 1/6. Then the bonus of each of c1 and c2 is at least x/2 - 1/12. Therefore, the bonus of B[i+1] is at least x-1/6, so sum(B[i]) + bonus(B[i+1]) ≥ (1-x)+(x-1/6) = 5/6.
We can apply the above inequality to successive pairs, and get: sum(B[1]) + bonus(B[2]) + sum(B[2]) + bonus(B[3]) + ... + sum(B[k-1]) + bonus(B[k]) ≥ 5/6*(k-1).
Therefore, the total weight of all FF bins is at least 5/6*(FF - 3) (where we subtract 3 for the single one-item bin with sum<1/2, single two-item bin with sum<2/3, and the k-1 from the two-item bins with sum ≥ 2/3).
All in all, we get that 17/12*OPT ≥ 5/6*(FF-3), so FF ≤ 17/10*OPT+3.
Dósa and Sgall present a tighter analysis that gets rid of the 3, and get that FF ≤ 17/10*OPT.

= Lower bound

=
There are instances on which the performance bound of 1.7OPT is tight. The following example is based on. The bin capacity is 101, and:

The sequence is: 6 (x7), 10 (x7), 16 (x3), 34 (x10), 51 (x10).
The optimal packing contains 10 bins: [51+34+16] (x3), [51+34+10+6] (x7). All bin sums are 101.
The First Fit packing contains 17 bins: [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5), [51] (x10).
The bin sums are: 92, 68, 68 (x5), 51 (x10).
The rewards (normalized to 101) are 0, 0, 16.8 (x5), 33.7 (x10).
The total weights (normalized to 101) are 92, 68, 84.8 (x5), 84.7 (x10). It can be seen that almost all weights are close to 101*5/6=84.1.

= Performance with divisible item sizes

=
An important special case of bin-packing is that which the item sizes form a divisible sequence (also called factored). A special case of divisible item sizes occurs in memory allocation in computer systems, where the item sizes are all powers of 2. If the item sizes are divisible, and in addition, the largest item sizes divides the bin size, then FF always finds an optimal packing.: Thm.3

Refined first-fit

Refined-First-Fit (RFF) is another online algorithm for bin packing, that improves on the previously developed FF algorithm. It was presented by Andrew Chi-Chih Yao.

= The algorithm

=
The items are categorized in four classes, according to their sizes (where the bin capacity is 1):

A

{\displaystyle A}

-piece - size in

(
1

/

2
,
1
]

{\displaystyle (1/2,1]}

.

B

1

{\displaystyle B_{1}}

-piece - size in

(
2

/

5
,
1

/

2
]

{\displaystyle (2/5,1/2]}

.

B

2

{\displaystyle B_{2}}

-piece - size in

(
1

/

3
,
2

/

5
]

{\displaystyle (1/3,2/5]}

.

X

{\displaystyle X}

-piece - size in

(
0
,
1

/

3
]

{\displaystyle (0,1/3]}

.
Similarly, the bins are categorized into four classes: 1, 2, 3 and 4.
Let

m
∈
{
6
,
7
,
8
,
9
}

{\displaystyle m\in \{6,7,8,9\}}

be a fixed integer. The next item

i
∈
L

{\displaystyle i\in L}

is assigned into a bin in -

Class 1, if

i

{\displaystyle i}

is an

A

{\displaystyle A}

-piece,
Class 2, if

i

{\displaystyle i}

is an

B

1

{\displaystyle B_{1}}

-piece,
Class 3, if

i

{\displaystyle i}

is an

B

2

{\displaystyle B_{2}}

-piece, but not the

(
m
k
)

{\displaystyle (mk)}

th

B

2

{\displaystyle B_{2}}

-piece seen so far, for any integer

k
≥
1

{\displaystyle k\geq 1}

.
Class 1, if

i

{\displaystyle i}

is the

(
m
k
)

{\displaystyle (mk)}

th

B

2

{\displaystyle B_{2}}

-piece seen so far,
Class 4, if

i

{\displaystyle i}

is an

X

{\displaystyle X}

-piece.
Once the class of the item is selected, it is placed inside bins of that class using first-fit bin packing.
Note that RFF is not an Any-Fit algorithm since it may open a new bin despite the fact that the current item fits inside an open bin (from another class).

= Approximation ratio

=
RFF has an approximation guarantee of

R
F
F
(
L
)
≤
(
5

/

3
)
⋅

O
P
T

(
L
)
+
5

{\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}

. There exists a family of lists

L

k

{\displaystyle L_{k}}

with

R
F
F
(

L

k

)
=
(
5

/

3
)

O
P
T

(

L

k

)
+
1

/

3

{\displaystyle RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3}

for

O
P
T

(
L
)
=
6
k
+
1

{\displaystyle \mathrm {OPT} (L)=6k+1}

.