TR-2019-11

Online 2-dimensional rectangular bin packing

Tamás Király, Lilla Lomoschitz



Abstract

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:

@techreport{egres-19-11,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Lomoschitz, Lilla},
TITLE = {Online 2-dimensional rectangular bin packing},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-11}
}


Last modification: 29.12.2019. Please email your comments to Tamás Király!