Harmonic bin packing

The Harmonic-k algorithm partitions the interval of sizes ${\displaystyle (0,1]}$ harmonically into ${\displaystyle k-1}$ pieces ${\displaystyle I_{j}:=(1/(j+1),1/j]}$ for ${\displaystyle 1\leq j<k}$ and ${\displaystyle I_{k}:=(0,1/k]}$ such that ${\displaystyle \bigcup _{j=1}^{k}I_{j}=(0,1]}$. An item ${\displaystyle i\in L}$ is called an ${\displaystyle I_{j}}$-item, if ${\displaystyle s(i)\in I_{j}}$.

The algorithm divides the set of empty bins into ${\displaystyle k}$ infinite classes ${\displaystyle B_{j}}$ for ${\displaystyle 1\leq j\leq k}$, one bin type for each item type. A bin of type ${\displaystyle B_{j}}$ is only used for bins to pack items of type ${\displaystyle j}$. Each bin of type ${\displaystyle B_{j}}$ for ${\displaystyle 1\leq j<k}$ can contain exactly ${\displaystyle j}$ ${\displaystyle I_{j}}$-items. The algorithm now acts as follows:

• If the next item ${\displaystyle i\in L}$ is an ${\displaystyle I_{j}}$-item for ${\displaystyle 1\leq j<k}$, the item is placed in the first (only open) ${\displaystyle B_{j}}$ bin that contains fewer than ${\displaystyle j}$ pieces or opens a new one if no such bin exists.
• If the next item ${\displaystyle i\in L}$ is an ${\displaystyle I_{k}}$-item, the algorithm places it into the bins of type ${\displaystyle B_{k}}$ using Next-Fit.

This algorithm was first described by Lee and Lee.[1] It has a time complexity of ${\displaystyle {\mathcal {O}}(n\log(n))}$ where n is the number of input items. At each step, there are at most ${\displaystyle 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 ${\displaystyle \sigma _{1}:=1}$, ${\displaystyle \sigma _{i+1}:=\sigma _{i}(\sigma _{i}+1)}$ for ${\displaystyle i\geq 1}$ and proved that for ${\displaystyle \sigma _{l}<k<\sigma _{l+1}}$ it holds that ${\displaystyle R_{Hk}^{\infty }\leq \sum _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))}$. For ${\displaystyle k\rightarrow \infty }$ it holds that ${\displaystyle R_{Hk}^{\infty }\approx 1.6910}$. Additionally, they presented a family of worst-case examples for that ${\displaystyle R_{Hk}^{\infty }=\sum _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))}$

The Refined-Harmonic combines ideas from the Harmonic-k algorithm with ideas from Refined-First-Fit. It places the items larger than ${\displaystyle 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 ${\displaystyle 1/2}$.

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

• An ${\displaystyle I_{a}}$-bin contains only one ${\displaystyle I_{a}}$-item.
• An ${\displaystyle I_{b}}$-bin contains only one ${\displaystyle I_{b}}$-item.
• An ${\displaystyle I_{a}b}$-bin contains one ${\displaystyle I_{a}}$-item and one ${\displaystyle I_{b}}$-item.
• An ${\displaystyle I_{b}b}$-bin contains two ${\displaystyle I_{b}}$-items.

An ${\displaystyle I_{b}'}$-bin denotes a bin that is designated to contain a second ${\displaystyle 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.[1] They proved that for ${\displaystyle k=20}$ it holds that ${\displaystyle R_{RH}^{\infty }\leq 373/228}$.

Modified Harmonic (MH) has asymptotic ratio ${\displaystyle R_{MH}^{\infty }\leq 538/33\approx 1.61562}$.[2]

Modified Harmonic 2 (MH2) has asymptotic ratio ${\displaystyle R_{MH2}^{\infty }\leq 239091/148304\approx 1.61217}$.[2]

Harmonic + 1 (H+1) has asymptotic ratio ${\displaystyle R_{H+1}^{\infty }\geq 1.59217}$.[3]

Harmonic ++ (H++) has asymptotic ratio ${\displaystyle R_{H++}^{\infty }\leq 1.58889}$[3] and ${\displaystyle R_{H++}^{\infty }\geq 1.58333}$.[3]