Harmonic bin packing explained

Harmonic bin-packing is a family of online algorithms for bin packing. The input to such an algorithm is a list of items of different sizes. The 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 harmonic bin-packing algorithms rely on partitioning the items into categories based on their sizes, following a Harmonic progression. There are several variants of this idea.

Harmonic-k

The Harmonic-k algorithm partitions the interval of sizes

( 0 , 1 ] harmonically into k -1 pieces I _{j} : = ( 1 /(j +1 ), 1 /j] for 1 \leq j < k and I _{k} : = ( 0 , 1 /k] such that c up ^{k} _{j =1} I _{j} = ( 0 , 1 ] . An item i \in L is called an I _{j} -item, if s(i) \in I _{j} .

The algorithm divides the set of empty bins into

k infinite classes B _{j} for 1 \leq j \leq k , one bin type for each item type. A bin of type B _{j} is only used for bins to pack items of type j . Each bin of type B _{j} for 1 \leq j < k can contain exactly j I _{j} -items. The algorithm now acts as follows:

• If the next item

i \in L is an I _{j} -item for 1 \leq j < k , the item is placed in the first (only open) B _{j} bin that contains fewer than j pieces or opens a new one if no such bin exists.

• If the next item

i \in L is an I _{k} -item, the algorithm places it into the bins of type B _{k} using Next-Fit.

This algorithm was first described by Lee and Lee.^[1] It has a time complexity of

l{O}(nlog(n)) where n is the number of input items. At each step, there are at most k open bins that can be potentially used to place items, i.e., it is a k-bounded space algorithm.

Lee and Lee also studied the asymptotic approximation ratio. They defined a sequence

\sigma _{1} : = 1 , \sigma _{i+1} : = \sigma _{i} (\sigma _{i} +1 ) for i \geq 1 and proved that for \sigma _{l} < k <\sigma _{l+1} it holds that R ^{inf ty} _{Hk} \leq \sum ^{l} _{i =1} 1 /\sigma _{i} + k/(\sigma _{l+1} (k -1 )) . For k → inf ty it holds that R ^{inf ty} _{Hk} ≈ 1 . 6910 . Additionally, they presented a family of worst-case examples for that R ^{inf ty} _{Hk} = \sum ^{l} _{i =1} 1 /\sigma _{i} + k/(\sigma _{l+1} (k -1 ))

Refined-Harmonic (RH)

The Refined-Harmonic combines ideas from the Harmonic-k algorithm with ideas from Refined-First-Fit. It places the items larger than

1 / 3 similar as in Refined-First-Fit, while the smaller items are placed using Harmonic-k. The intuition for this strategy is to reduce the huge waste for bins containing pieces that are just larger than 1 / 2 .

The algorithm classifies the items with regard to the following intervals:

I _{1} : = ( 59 / 96 , 1 ] , I _{a} : = ( 1 / 2 , 59 / 96 ] , I _{2} : = ( 37 / 96 , 1 / 2 ] , I _{b} : = ( 1 / 3 , 37 / 96 ] , I _{j} : = ( 1 /(j +1 ), 1 /j] , for j \in \{ 3 , ... , k -1 \} , and I _{k} : = ( 0 , 1 /k] . The algorithm places the I _{j} -items as in Harmonic-k, while it follows a different strategy for the items in I _{a} and I _{b} . There are four possibilities to pack I _{a} -items and I _{b} -items into bins.

• An

I _{a} -bin contains only one I _{a} -item.

• An

I _{b} -bin contains only one I _{b} -item.

• An

I _{ab} -bin contains one I _{a} -item and one I _{b} -item.

• An

I _{bb} -bin contains two I _{b} -items.

An

I _{b'} -bin denotes a bin that is designated to contain a second I _{b} -item. The algorithm uses the numbers N_a, N_b, N_ab, N_bb, and N_b' to count the numbers of corresponding bins in the solution. Furthermore, N_c= N_b+N_ab Algorithm Refined-Harmonic-k for a list L = (i_1, \dots i_n): 1. N_a = N_b = N_ab = N_bb = N_b' = N_c = 0 2. If i_j is an I_k-piece then use algorithm Harmonic-k to pack it 3. else if i_j is an I_a-item then if N_b != 1, then pack i_j into any J_b-bin; N_b--; N_ab++; else place i_j in a new (empty) bin; N_a++; 4. else if i_j is an I_b-item then if N_b' = 1 then place i_j into the I_b'-bin; N_b' = 0; N_bb++; 5. else if N_bb <= 3N_c then place i_j in a new bin and designate it as an I_b'-bin; N_b' = 1 else if N_a != 0 then place i_j into any I_a-bin; N_a--; N_ab++;N_c++ else place i_j in a new bin; N_b++;N_c++This algorithm was first described by Lee and Lee. They proved that for k = 20 it holds that R ^{inf ty} _{RH} \leq 373 / 228 .

Other variants

Modified Harmonic (MH) has asymptotic ratio

R ^{inf ty} _{MH} \leq 538 / 33 ≈ 1 . 61562 .^[2]

Modified Harmonic 2 (MH2) has asymptotic ratio

R ^{inf ty} _{MH 2} \leq 239091 / 148304 ≈ 1 . 61217 .

Harmonic + 1 (H+1) has asymptotic ratio

R ^{inf ty} _{H +1} \geq 1 . 59217 .^[3]

Harmonic ++ (H++) has asymptotic ratio

R ^{inf ty} _{H ++} \leq 1 . 58889 and R ^{inf ty} _{H ++} \geq 1 . 58333 .

References

1. Lee. C. C.. Lee. D. T.. July 1985. A simple on-line bin-packing algorithm. Journal of the ACM. 32. 3. 562–572. 10.1145/3828.3833. 15441740. free.
2. Ramanan. Prakash. Brown. Donna J. Lee. C.C. Lee. D.T. September 1989. On-line bin packing in linear time. Journal of Algorithms. 10. 3. 305–326. 10.1016/0196-6774(89)90031-X. free. 2142/74206.
3. Seiden. Steven S.. 2002. On the online bin packing problem. Journal of the ACM. 49. 5. 640–671. 10.1145/585265.585269. 14164016.