Harmonic bin packing

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

The algorithm divides the set of empty bins into $k$ infinite classes $B\_j$ for $1\backslash leq\; j\; \backslash 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 can contain exactly $j$ $I\_j$-items. The algorithm now acts as follows:

• If the next item $i\; \backslash in\; L$ is an $I\_j$-item for , 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\; \backslash 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.{{cite journal|last1=Lee|first1=C. C.|last2=Lee|first2=D. T.|date=July 1985|title=A simple on-line bin-packing algorithm|journal=Journal of the ACM|volume=32|issue=3|pages=562–572|doi=10.1145/3828.3833|s2cid=15441740|doi-access=free}} It has a time complexity of $\backslash mathcal\{O\}(n\backslash log(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 $\backslash sigma\_1\; :=\; 1$, $\backslash sigma\_\{i+1\}\; :=\; \backslash sigma\_\{i\}(\backslash sigma\_\{i\}+1)$ for $i\; \backslash geq\; 1$ and proved that for it holds that $R\_\{Hk\}^\{\backslash infty\}\; \backslash leq\; \backslash sum\_\{i\; =\; 1\}^\{l\}\; 1/\backslash sigma\_i\; +\; k/(\backslash sigma\_\{l+1\}(k-1))$. For $k\; \backslash rightarrow\; \backslash infty$ it holds that $R\_\{Hk\}^\{\backslash infty\}\; \backslash approx\; 1.6910$. Additionally, they presented a family of worst-case examples for that $R\_\{Hk\}^\{\backslash infty\}\; =\; \backslash sum\_\{i\; =\; 1\}^\{l\}\; 1/\backslash sigma\_i\; +\; k/(\backslash 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 $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\; \backslash in\; \backslash \{3,\; \backslash dots,\; k-1\backslash \}$, 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\text{'}$-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^\backslash infty\_\{RH\}\; \backslash leq\; 373/228$.

Modified Harmonic (MH) has asymptotic ratio $R\_\{MH\}^\{\backslash infty\}\; \backslash leq\; 538/33\; \backslash approx\; 1.61562$.{{cite journal|last1=Ramanan|first1=Prakash|last2=Brown|first2=Donna J|last3=Lee|first3=C.C|last4=Lee|first4=D.T|date=September 1989|title=On-line bin packing in linear time|journal=Journal of Algorithms|volume=10|issue=3|pages=305–326|doi=10.1016/0196-6774(89)90031-X|hdl-access=free|hdl=2142/74206}}

Modified Harmonic 2 (MH2) has asymptotic ratio $R\_\{MH2\}^\{\backslash infty\}\; \backslash leq\; 239091/148304\; \backslash approx\; 1.61217$.

Harmonic + 1 (H+1) has asymptotic ratio $R\_\{H+1\}^\backslash infty\; \backslash geq\; 1.59217$.{{cite journal|last1=Seiden|first1=Steven S.|date=2002|title=On the online bin packing problem|journal=Journal of the ACM|volume=49|issue=5|pages=640–671|doi=10.1145/585265.585269|s2cid=14164016}}

Harmonic ++ (H++) has asymptotic ratio $R\_\{H++\}^\backslash infty\; \backslash leq\; 1.58889$ and $R\_\{H++\}^\{\backslash infty\}\; \backslash geq\; 1.58333$.

Category:Bin packing