Refined first-fit bin packing

Refined-First-Fit (RFF) 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 RFF algorithm uses a sophisticated heuristic, that improves on the previously-developed first-fit bin packing algorithm. This algorithm was presented by Andrew Chi-Chih Yao.

The algorithm

The items are categorized in four classes, according to their sizes:

• [math]\displaystyle{ A }[/math]-piece - size in [math]\displaystyle{ (1/2,1] }[/math].
• [math]\displaystyle{ B_1 }[/math]-piece - size in [math]\displaystyle{ (2/5,1/2] }[/math].
• [math]\displaystyle{ B_2 }[/math]-piece - size in [math]\displaystyle{ (1/3,2/5] }[/math].
• [math]\displaystyle{ X }[/math]-piece - size in [math]\displaystyle{ (0,1/3] }[/math].

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

Let [math]\displaystyle{ m \in \{6,7,8,9\} }[/math] be a fixed integer. The next item [math]\displaystyle{ i \in L }[/math] is assigned into a bin in -

• Class 1, if [math]\displaystyle{ i }[/math] is an [math]\displaystyle{ A }[/math]-piece,
• Class 2, if [math]\displaystyle{ i }[/math] is an [math]\displaystyle{ B_1 }[/math]-piece,
• Class 3, if [math]\displaystyle{ i }[/math] is an [math]\displaystyle{ B_2 }[/math]-piece, but not the [math]\displaystyle{ (mk) }[/math]th [math]\displaystyle{ B_2 }[/math]-piece seen so far, for any integer [math]\displaystyle{ k \geq 1 }[/math].
• Class 1, if [math]\displaystyle{ i }[/math] is the [math]\displaystyle{ (mk) }[/math]th [math]\displaystyle{ B_2 }[/math]-piece seen so far,
• Class 4, if [math]\displaystyle{ i }[/math] is an [math]\displaystyle{ X }[/math]-piece.

Once the class of the item is selected, it is placed inside items 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 [math]\displaystyle{ RFF(L) \leq (5/3) \cdot \mathrm{OPT}(L) +5 }[/math]. There exists a family of lists [math]\displaystyle{ L_k }[/math] with [math]\displaystyle{ RFF(L_k) = (5/3)\mathrm{OPT}(L_k) +1/3 }[/math] for [math]\displaystyle{ \mathrm{OPT}(L) = 6k+1 }[/math].