Online Packing of Orthogonal Polygons

Rectangle packings has been studied for almost 50 years. A straightforward reduction from partition shows that the offline strip packing problem cannot be approximated with an absolute factor better than 3/2 unless $𝖯=\mathrm{𝖭𝖯}$, and the best known approximation ratio is $5/3+\epsilon$ by Harren, Jansen, Prädel, and Van Stee [35]. For the online variant, first fit shelf algorithms as proposed by Baker and Schwarz [10], are widely studied. The best known competitive ratio of $7/2+\sqrt{10}\approx 6.66$ is achieved by Ye, Han, and Zhang [52]. Restricting the attention to large instances, the best asymptotic competitive ratio is lower bounded by $1.54$ by van Vliet [51] and upper bounded by $1.59$ by Han, Iwama, Ye, and Zhang [32].

For bin packing of rectangles under translation, there exist approximation algorithms with approximation ratio 2 [34] and asymptotic approximation guarantee $1.4$ by Bansal and Khan [14]. For online bin packing of rectangles, the upper bound on the asymptotic competitive ratio for online translational bin packing axis-parallel rectangular pieces into unit square bins has been decreased in a series of papers from $3.25$ [20] to about $2.55$ by Han, Chin, Ting, Zhang and Zhang [31] and the lower bound has been increased from $1.6$ [29] to $1.91$ by Epstein [23]. For the special case of squares, the lower bound is approximately 1.75 due to Balogh, Békési, Dósa, Epstein, and Levin [11], while the upper bound is above 2.08 by Epstein and Mualem [25].

For the problem of area minimization, Abrahamsen and Beretta [3] present $O(n)$-competitive algorithms and show a lower bound of $\mathrm{\Omega }(n)$ for both versions of rotation allowed and translations only. For perimeter minimization, they gave a $3.98$-competitive algorithm for both, translation and rotation, as well as a lower bound on the competitive ratio of $4/3$ for the case of translation and of $5/4$ for the case of rotation.

Constant-factor approximations for packing convex polygons exist for many variants [7, 8, 1, 41]; an exception is bin packing where constant approximation factors are only known if the diameter of the items is bounded by a constant. In contrast to these constant guarantees, for online translational packings of convex polygons, Aamand, Abrahamsen, Beretta and Kleist [1] show that strip packing, bin packing, and perimeter packing do not allow for constant competitive online algorithms, even if all pieces have a diameter bounded by an arbitrarily small constant. To this end, they reduce to an online sorting problem which sparked follow-up investigations [2, 9, 47]. Concerning upper bounds, they give an online algorithm with competitive ratio $O(n^{0.59})$ for strip packing. The knapsack problem for convex polygons under rigid motions is studied by Merino and Wiese [45].

We identified interesting connections between packings of special L-shapes and scheduling problems such as open end bin packing and machine minimization. These yield algorithms for large and symmetric L-shapes in the case where all L-shapes have equal lengths or equal widths; for an overview see Table 3.

The case of equal lengths is related to open end bin packing. In a variant of classical 1D bin packing known as ordered open end bin packing, items of sizes in (0, 1] are presented one by one, and must be assigned to bins in this order. An item can be assigned to any bin for which the current total size is strictly below 1, i.e., the bin can be overloaded by its last packed item. Balogh, Epstein, and Levin [13] present a $2$-competitive online algorithm and Epstein [24] designs a $1.5$ approximation. As packings of large, symmetric L-shapes of equal lengths can be reduced to open end bin packing, we obtain offline and online algorithms with constant factors. Specifically, for packing L-shapes of length $\mathrm{\ell }$, we consider open end bins of capacity $1-\mathrm{\ell }$. An L-shape $L_i$ with arm length $\mathrm{\ell }$ and width $w_i$ is associated with a real $r_i:=w_i$. It is easy to see that an $L_i$ can be packed into a bin containing $L_1,\mathrm{\dots },L_k$ (bottom-leftmost) if ${\sum }_{j=1}^k{w}_j+\mathrm{\ell }\le 1$. Similarly, $r_i$ can be packed into an open bin containing $r_1,\mathrm{\dots },r_k$ if (and only if) ${\sum }_{j=1}^k{r}_j\le 1-\mathrm{\ell }$. As these conditions are equivalent, solutions of open end bin packing translate to (bottom-leftmost) packings of large, symmetric L-shapes of equal lengths. This implies a 2-competitive online algorithm and a 1.5-approximation in this case.

For bin packing of large and symmetric L-shapes with different lengths, we identified a close connection to the machine minimization problem: Given a set of jobs, each of which has a release time $r$, a processing time $p$ and deadline $d$, the task is to schedule these jobs on a minimum number of machines such that each machine processes at most one job at a time and each job starts not before its release time, and finishes not after its deadline. For large and symmetric L-shapes, we show that the two parameters, length $\mathrm{\ell }$ and width $w$, translate to a job with release time $0$, processing time $w$, and deadline $1-\mathrm{\ell }$. Therefore, we present relevant work in the context of machine minimization. Yu and Zhang [53] present approximation algorithms for the special cases of equal deadlines and equal processing times. In particular, their 2-approximation algorithm for the special case of equal deadlines translates to a 2-approximation for offline bin packing of large, symmetric L-shapes. Kao, Chen, Rutter, and Wagner [38, Lemmas 1 and 2] present a polynomial algorithm that computes the offline optimal solution for jobs of unit processing times. This translates to a polyomial time algorithm for offline packings of instances where all L-shapes are large, symmetric, and have equal widths. Devanur, Makarychev, Panigrahi, and Yaroslavtsev [22, Section 2,3] present an $e$-competitive online algorithm for unit processing times; they also show that the competitive ratio of $e$ is optimal. This result is also implied by Bansal, Kimbrel, and Pruhs [15, Lemmas 4.7 and 4.8]. The insights can be translated to an $e$-competitive algorithm for packing large, symmetric L-shapes of equal widths. Moreover, Devanur et al. [22] present a 16-competitive online algorithm for the case with equal deadlines; their techniques are the basis of our 33-competitive algorithm for packing large symmetric L-shapes, namely Theorem 3(a).

There are many more results on the general case of machine minimization. However, due to a lower bound of $n$ by Saha [48], most subsequent work allows preemption of the jobs [18, 17, 36], a setting that does not carry over to packings of L-shapes.

For a given container of volume $C$ and a class of objects in ${ℝ}^d$, the critical density is the largest value of $V/C$ such that any sequence of objects of the class with a total volume of at most $V$ can always be packed in the container. For convex bodies of bounded diameter in ${ℝ}^3$, Auerbach, Banach, Mazur and Ulam [44] stated (without proof) that the critical density is positive, i.e., there exists a function $f$ such that any sequence of convex bodies in ${ℝ}^3$, each of diameter $\le \delta$ and total volume of at most $V$, can be packed into a cube with side length $s=f(\delta ,V)$ when rotations are allowed. The first proof, even for arbitrary dimension, is given by Kosiński [40]. When rotations are not allowed, Alt, Cheong, Park, and Scharf [6] showed that the critical density of packing convex bodies of bounded diameter into a cube is $0$; in particular for packing unit disks in ${ℝ}^3$. However, for cubes, Moon and Moser [46] showed that any sequence of cubes in ${ℝ}^d$ of total volume $1/2^{d-1}$ can be packed into the unit cube. This bound is the best possible, because for any $\epsilon >0$, two cubes with side lengths $1/2+\epsilon$ cannot be packed in the unit cube.

The study of critical densities likewise makes sense when the pieces appear in an online fashion. A lower bound on the critical density of online packing squares into the unit square has been improved in a sequence of papers [37, 16, 33, 27] from $5/16$ [37] to $2/5$ [16]. Interestingly, Januszewski and Lassak [37] proved that in dimension $d\ge 5$, the critical density of online packing cubes into the unit cube is $1/2^{d-1}$, just as in the offline case. Lassak and Zhang [42] showed that for some constant $\delta (d)>0$, any sequence of axis-parallel boxes of diameter and total area at most $\delta (d)$ can be packed online in the $d$-dimensional unit hypercube using translations. This implies that the critical packing density for convex bodies is positive for any dimension $d\ge 1$ when rotations are allowed as each body can be rotated so that it has a constant (depending on the dimension) density in its axis-parallel bounding box. In contrast, for translational and online packing convex polygons, Aamand, Abrahamsen, Beretta and Kleist [1] show that the critical packing density is $0$.

We show that Presenter has a strategy to present $n$ numbers such that Algorithm uses at least $n/\lfloor \log (k+1)\rfloor$ arrays while $\lceil n/k\rceil$ arrays would suffice. The idea is as follows: Consider a partially filled array $A$. The numbers in $A$ partition it into maximal sections of free slots. If a new number shall be inserted in $A$, it may be placed into at most one of these sections, since the entries in the array must be increasing. We say that two (possible future) numbers are similar with respect to $A$ if they must be placed in the same section. The idea of Presenter is to maintain a set of active numbers that are similar for all arrays.

In order to present $n$ natural numbers $a_1,\mathrm{\dots },a_n$, Presenter maintains the following invariant: In the beginning of iteration $i$, it has an active set of $2^{n-i+1}-1$ similar numbers. In the very beginning (of iteration 1), the set is $(0,2^n):=\{1,\mathrm{\dots },2^n-1\}$, each array has one section containing all slots, and Presenter presents $a_1=2^{n-1}$. In iteration $i+1$, Presenter determines the next number to be presented based on the action of Algorithm in iteration $i$. Algorithm places $a_i$ in a section of some array which results in two smaller sections. If the smaller of the two section lies to the left of $a_i$, then the active set $(l,r)$ is updated to $(l,a_i)$ and $a_{i+1}=(l+a_i)/2=a_i-2^{n-(i+1)}$; otherwise it is updated to $(a_i,r)$ and $a_{i+1}=(a_i+r)/2=a_i+2^{n-(i+1)}$. As the new active set is a subset of the previous, Algorithm must place numbers presented in the future in (subsets of) the current sections of the active set. By construction, the numbers of the active set remain similar. The active set is non-empty for at least $n$ iterations because it contains $2^{n-i+1}-1\ge 1$ numbers if $i\le n$.

When we restrict our attention to a fixed array with $k$ slots, then the section for the active numbers is (at least) halved each time a number is inserted; this is because we ensure that the active set must be inserted in the smaller section. Therefore, Algorithm can place at most $\lfloor \log (k+1)\rfloor$ of the $n$ numbers in each array and thus needs at least $\lceil n/\lfloor \log \left(k+1\right)\rfloor \rceil$ bins. This yields a competitive ratio of at least $\lceil n/\lfloor \log \left(k+1\right)\rfloor \rceil /\lceil n/k\rceil \in \mathrm{\Omega }(k/\log k)$. $◀$

We remark that the lower bound of Lemma 7 is tight, that is, there exists an online algorithm BinSorting$[k]$ that matches this bound.

For each partially filled array and any number, the valid slots form a consecutive interval. Clearly, in an empty array, all slots are valid. Let $𝒜$ denote the algorithm that places a new number in the first array with a valid slot, and in particular, in the middle slot of the section. With this choice, the smallest section of an array containing $m$ numbers has length $\ge \lfloor \left(k+1\right)/2^m\rfloor -1$. Therefore each array contains at least $\lfloor \log (k+1)\rfloor$ numbers before a new array is opened. Consequently, $𝒜$ uses at most $\lceil n/\lfloor \log \left(k+1\right)\rfloor \rceil$ arrays while $\text{OPT}=\lceil n/k\rceil$. $◀$

By construction up to $k$ items of ${ℒ}^k$ fit into one bin in descending order of their indices: With respect to the $x$-coordinate, exactly $k$ items can be packed next to each other. For the $y$-coordinate, we note the following. When $L_i$ is placed somewhere in the bin, the free space above is lower bounded by

So when placed in descending order, there is space for $k$ items. Figure 5(c) depicts an example for $k=8$. It remains to show that $L_i$ cannot be placed below/left of $L_j$ when . It cannot be placed entirely to the left of $L_j$, because $l_x(L_i)+l_x(L_j)=2(1/2+1/k)>1$, and it cannot be placed below $L_j$ because $w_y(L_i)+{\mathrm{\ell }}_y(L_j)=2^{-i-1}+1-2^{-j-1}>1$. $◀$

We now show how an algorithm for L-BinPack yields an algorithm for BinSorting$[k]$.

Let $𝒜$ be an $\alpha$-competitive algorithm for L-BinPack and consider an instance $I_S$ of BinSorting $[k]$ with $n$ numbers. We describe an online algorithm ${𝒜}^{\prime }$ for BinSorting$[k]$ which uses $𝒜$ as a subroutine. For each presented number $i$, ${𝒜}^{\prime }$ presents $L_i\in {ℒ}^k$ to $𝒜$. By Lemma 9, at most $k$ L-shapes of ${ℒ}^k$ fit into one bin. Let $x$ denote the $x$-coordinate of the reference point of $L_i$ in the $j$th bin as assigned by $𝒜$. Then ${𝒜}^{\prime }$ places number $i$ in the slot $\lfloor x\cdot 2k\rfloor +1$ of the $j$th array. As $x\in [0,1/2-1/2k]$, it holds that $\lfloor x\cdot 2k\rfloor +1\in [k]$. We shortly argue that this position is valid. Firstly, because all L-shapes have width $1/2k$, the assigned $x$-values differ by at least $1/2k$ and for any $x$ and $x^{\prime }$ with $|x-x^{\prime }|\ge 1/2k$, we have $|\lfloor x\cdot 2k\rfloor -\lfloor x^{\prime }\cdot 2k\rfloor |\ge 1$. Secondly, as $𝒜$ guarantees that the numbers of each array are increasing, the same holds for the indices of the L-shapes. Hence, by Lemma 9, the placement is valid. Consequently, we may translate the $x$-position of $L_i$ in the $j$th bin to a unique slot in the $j$th array. The number of used arrays equals the number of used bins. Moreover, the offline optimum is $\lceil n/k\rceil$ in both problems. Hence, ${𝒜}^{\prime }$ is $\alpha$-competitive. $◀$

Together, Lemmas 7 and 10 show the following statement, which proves Theorem 2.