The classical one-dimensional bin packing problem has several generalizations. This paper is concerned with a two-dimensional version where the bins are rectangles of fixed size $a \times 1$, and the rectangular items can be rotated by $90^\circ$. We provide an online algorithm for the problem and an upper bound on the asymptotic competitive ratio that goes from $\approx 2.57$ at $a=4/3$ to $\approx 2.46$ at $a=2$, and tends to 1.82 as $a \rightarrow \infty$. Additionally, for any constant space bounded online algorithm, a lower bound as a function of $a$ is also given. The lower bound is $\approx 2.15$ at $a=4/3$, remains above $1.8$ for $a<2+1/3$, and tends to $\approx 1.69$ as $a \rightarrow \infty$.
Bibtex entry:
AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s and Lomoschitz, Lilla}, |
TITLE | = | {Online 2-dimensional rectangular bin packing}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2019}, |
NUMBER | = | {TR-2019-11} |