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.

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:

This algorithm was first described by Lee and Lee. 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.