We study certain adversary sequences for online strip packing which were first designed and investigated by Brown, Baker and Katseff (Acta Inform. 18:207–225) and determine the optimal competitive ratio for packing such Brown-Baker-Katseff sequences online. As a byproduct of our result, we get a new lower bound of \(\rho \ge 3/2+\sqrt{33}/6 \approx 2.457\) for the competitive ratio of online strip packing.
1 Introduction
In the two-dimensional strip packing problem a number of rectangles have to be packed without rotation or overlap into a strip such that the height of the strip used is minimum. The width of the rectangles is bounded by 1 and the strip has width 1 and infinite height. Baker et al. (1980) show that this problem is NP-hard.
We study the online version of this packing problem. In the online version the rectangles are given to the online algorithm one by one from a list, and the next rectangle is given as soon as the current rectangle is irrevocably placed into the strip. To evaluate the performance of an online algorithm we employ competitive analysis. For a list of rectangles L, the height of a strip used by online algorithm A and by the optimal solution is denoted by A(L) and OPT(L), respectively. The optimal solution is not restricted in any way by the ordering of the rectangles in the list. Competitive analysis measures the absolute worst-case performance of online algorithm A by its competitive ratio supL{A(L)/OPT(L)} (cf. Pruhs et al. 2004).
Anzeige
Regarding the upper bound on the competitive ratio for online strip packing, recent advances have been made by Ye et al. (2009) and Hurink and Paulus (2008). Independently they show that a modification of the well-known shelf algorithm yields an online algorithm with competitive ratio \(7/2+\sqrt{10}\approx6.6623\). We refer to these two papers for a more extensive overview of the literature.
In the early 80’s, Brown et al. (1982) derived a lower bound ρ≥2 on the competitive ratio of any online algorithm by constructing certain (adversary) sequences in a fairly straightforward way (cf. Sect. 2). These sequences were further studied by Johannes (2006) and Hurink and Paulus (2008), who derived improved lower bounds of 2.25 and 2.43, resp. (Both results are computer aided and presented in terms of online parallel machine scheduling, a closely related problem.) The paper of Hurink and Paulus (2008) also presents an upper bound of ρ≤2.5 for packing such “Brown-Baker-Katseff sequences”. The purpose of our present paper is to close the gap between 2.43 and 2.5 by presenting a tight analysis, showing that Brown-Baker-Katseff sequences can be packed online with competitive ratio \(\rho = 3/2 +\sqrt{33}/6\) and that this is best possible. As a byproduct, we obtain a new lower bound ρ≈2.457 for online strip packing.
The result of this paper has been presented at the CTW 2010 (cf. Kern 2010). Meanwhile, in a joint work with R. Harren, we tried to analyze a modified version of Brown-Baker-Katseff sequences, yielding a slightly better lower bound (but no exact analysis as here), cf. Harren and Kern (2011).
2 The instance construction
In this section we describe the construction of Brown-Baker-Katseff sequences Ln according to Brown et al. (1982). In addition, we present an online algorithm for packing the sequences Ln online with ratio \(\hat{\rho}= 3/2+\sqrt{33}/6\). For convenience, let throughout this note \(\hat{\rho}=3/2+\sqrt{33}/6\).
Anzeige
We define Ln as the list of rectangles (p0,q1,p1,q2,p2,…,qn,pn), where pi denotes a rectangle of height pi and negligible width (no more than 1/(n+1)), and qi denotes a rectangle of height qi and width 1. The rectangle heights are defined such that, when the items are packed online, each item must be packed on top of the preceding ones. More precisely, we let
where αipi and βipi are distances the online algorithm has placed between earlier rectangles, and ϵ is a small positive value. The value αipi denotes the vertical distance between rectangles pi−1 and qi, and the value βipi denotes the vertical distance between qi and pi. This is illustrated in Fig. 1. The values αi and βi completely characterize the behavior of the online algorithm when processing Ln. For consistency we define in addition α0=0.
×
By definition of the rectangles’ heights and widths, an online algorithm can only pack the rectangles one above the other in the same order as the rectangles appear in the list Ln. An optimal offline packing is obtained by first packing the rectangles qi on top of each other and then pack all pi next to each other on top of the q-rectangles. The sole function of the positive term ϵ is to ensure this structure on any online packing. From now on we assume that ϵ is small enough to be omitted from the analysis.
We start with the (simpler) upper bound:
Theorem 1
Each listLncan be packed online with competitive ratio\(\hat{\rho}=\frac{3}{2}+\frac{\sqrt{33}}{6}\).
Proof
Consider the online algorithm A that chooses \(\beta_{0}=\hat{\rho}-1\), \(\alpha_{2}=1/(\hat{\rho}-1)\), and all other gaps equal to 0. So \(p_{0}=1,q_{1}=q_{2}=\hat{\rho}-1, p_{1}=\hat{\rho}\), and p2 can be computed from p2=p1+α2p2: We get \(p_{2}=\hat{\rho}/(1-\frac{1}{\hat{\rho}-1})=\frac{(\hat{\rho}-1)\hat{\rho}}{\hat{\rho}-2}\), or \(p_{2}= (\hat{\rho}-1)(3\hat{\rho}-2)=4\hat{\rho}-2\) by our choice of \(\hat{\rho}\).
We claim that the resulting algorithm is \(\hat{\rho}\)-competitive when presented with Ln.
After packing p0=1 we have \(A(L_{0})=\hat{\rho}\) and OPT(L0)=1. Thus, the competitive ratio is exactly \(\hat{\rho}\) at this point.
After packing rectangle q1 the online and optimal packing increase by the same amount. Thus the competitive ratio decreases.
After \(p_{1}=\hat{\rho}\) we have \(A(L_{1})=\beta_{0} p_{0} +p_{0}+q_{1}+p_{1}=\hat{\rho}-1+1+\hat{\rho} -1 +\hat{\rho}\), while OPT(L1)=q1+p1=2ρ−1. Hence \({A(L_{1})}/{\mathit{OPT}(L_{1})}=(3\hat{\rho}-1)/(2\hat{\rho}-1)<\hat{\rho}\).
After q2 we have \(A(L_{1}q_{2})=A(L_{1})+q_{2}+\alpha_{2}p_{2}=3\hat{\rho}-1+\hat{\rho}-1+3\hat{\rho}-2=7\hat{\rho}-4\), while OPT(L1q2)=p1+q1+q2=3ρ−2. So \({A(L_{1}q_{2})}/{\mathit{OPT}(L_{1}q_{2})}=(7\hat{\rho}-4)/(3\hat{\rho}-2)=\hat{\rho}\). Again the competitive ratio is exactly \(\hat{\rho}\) at this point (by definition of \(\hat{\rho}\)).
After p2 we have \(A(L_{2})=A(L_{1}q_{2})+p_{2}=7\hat{\rho}-4+4\hat{\rho}-2=11\hat{\rho}-6\), while \(\mathit{OPT}(L_{2})=q_{1}+q_{2}+p_{2}=2\hat{\rho}-2+4\hat{\rho}-2=6\hat{\rho}-4\). Thus \({A(L_{2})}/{\mathit{OPT}(L_{2})}=(11\hat{\rho}-6)/(6\hat{\rho}-4)<\hat{\rho}\).
For i≥3 there are no more gaps introduced by online algorithm A. In particular, \(p_{2}=p_{3}=p_{4}=\cdots=(\hat{\rho}-1)(3\hat{\rho}-2) \) and \(q_{i}=\alpha_{2}p_{2}=3\hat{\rho}-2\) for all i≥3. When packing qi, the online and optimal packing increase by the same amount and, thus, ρ-competitiveness is not violated. After packing pi+1, however, we have OPT(Li+1)=OPT(Li)+qi+1 and \(A(L_{i+1})=A(L_{i})+q_{i+1}+p_{i+1}=A(L_{i})+\hat{\rho}q_{i+1}\). The height of the online packing grows exactly \(\hat{\rho}\) times as fast as the optimal packing.
So, online algorithm A is \(\hat{\rho}\)-competitive for the list of rectangles Ln. □
3 Lower bound on the competitive ratio
In this section we prove a lower bound of \(\hat{\rho}={3}/{2}+{\sqrt{33}}/{6}\) on the competitive ratio for online packing Brown-Baker-Katseff sequences—and hence for online strip packing in general. The outline of the proof is as follows.
Assume that there exists a ρ-competitive online algorithm A with \(\rho<\hat{\rho}\). We present this algorithm with the list Ln, with n arbitrarily large. To obtain a contradiction we define a potential function Φi on the state of the online packing after packing rectangle pi. We argue that this potential function is both bounded from below and that it decreases to −∞, giving us the required contradiction.
After packing the rectangle pi, we measure with γi how much online algorithm A improves upon the ρ-competitiveness bound: We define γi through
$$A(L_i)+\gamma_ip_i=\rho \mathit{OPT}(L_i).$$
The potential function Φi is defined (after packing rectangle pi) by
We admit that the potential function looks rather involved. Its exact form is simply motivated by the technical analysis that follows. In particular, the potential function is designed such that a certain “shift invariance” (cf. Lemma 2 below) holds, which helps a lot in simplifying the analysis. (Yet, in Harren and Kern 2011 we analyze “extended” Brown-Baker-Katseff sequences with a simpler potential Φi=γi+βi and considerable technical effort.)
The values of αi and βi are nonnegative by definition and γi is nonnegative by the ρ-competitiveness of online algorithm A. Observe that shifting pi, say, upward, increases βi and decreases γi by the same amount, so that shifting pi has actually no effect on Φi. In Lemma 2 we will see that the same holds w.r.t. shifting qi. Thus the decisions of the online algorithm in “phase i” have no effect on Φi, but rather on subsequent potential values. (This phenomenon is observed also elsewhere, cf., e.g. Fuchs et al. 2005 or Harren and Kern 2011.) The crucial result is Lemma 6, stating that \(\rho <\hat{\rho}\) forces a significant decrease of the potential in each step. Thus Φi+1→−∞ for i→∞. On the other hand, in Lemma 5 we show among other things that \(\alpha_{i} < 1/(\hat{\rho}-1)\). As a consequence, Φi>−1 for all i. This contradiction finally implies \(\rho \ge \hat{\rho}\), the main result of this note:
Theorem 2
The best possible ratio for packing Brown-Baker-Katseff sequences is\(\hat{\rho}=3/2+\sqrt{33}/6\). This value also provides a lower bound for online strip packing.
The remainder of this note is concerned with the proofs of the afore mentioned lemmata. We start by providing some basic properties (Lemmas 1 and 2 below) of the potential function Φi. In the following, ρ is assumed to be suitably close to \(\hat{\rho}\) whenever this is necessary.
First observe that the following equation defines pi+1 according to the construction rule for the list Ln. We will use it at several places during our analysis:
(1)
Lemma 1
If Φi≤ρ−1 thenγi+βi+αi≤ρ−1.
Proof
□
Lemma 2
The potential Φiis invariant under shiftingpiand/orqi.
Proof
Shifting rectangle pi, say, upward by one unit does not affect OPT(Li) nor αi. Furthermore, A(Li) increases by one unit and, hence, γipi decreases by one unit. At the same time βipi increases by one unit, so that γi+βi remains constant and Φi is invariant under shifting pi.
To show that Φi is invariant under shifting qi, assume w.l.o.g. that βi=0, i.e., that pi has been shifted down to qi, and that we shift the concatenated rectangles qipi simultaneously, say, upward. This causes an increase of pi by one unit, so A(Li) increases in total by 2 units. On the other hand, OPT(Li) increases by just one unit, so γipi will increase by ρ−2 units. Clearly, αipi increases by one unit and (1−αi)pi=(1+βi−1)pi−1 remains constant. Hence
Clearly, shifting pi and/or qidoes have an effect on subsequent values like pi+1 and Φi+1. Furthermore, even when we are only interested in packing Li, shifting up pi or shifting down the concatenated qipi may result in an infeasible packing. (Indeed, as we shift qipi down, pi decreases and after a while the packing may cease to be ρ-competitive!) As long as we are only interested in the value of Φi, however, we may well shift pi and qi as we like, disregarding the competitiveness constraints. We will make extensive use of this observation further on.
By Lemma 2 we can shift rectangle pi+1 down, i.e. βi+1=0. Then
By (1) we can divide the left hand side by (1−αi+1)pi+1 and the right hand side by (1+βi)pi to obtain the result. □
Lemma 4
Ifqi+1=max{αipi,qi}, then we may assume w.l.o.g. thatβi=0.
Proof
Shifting rectangle pi down decreases the distance βipi and increases αi+1pi+1. However, when we keep all other distances equal it does not affect pj with j>i. Due to the increase in αi+1pi+1 some qj with j>i may increase, but this is only in favor of the online algorithm since the optimal value increases by exactly the same amount. So the alternative online algorithm that schedules pi earlier and leaves all other distances unchanged is also feasible. □
Lemma 5
Fori≥0, Φi≤ρ−1, and fori≥1, \(\alpha_{i}\leq 1/(\hat{\rho}-1)\)and\(q_{i}/p_{i}\leq 1(\hat{\rho}-1)\). In caseqi=αi−1pi−1orqi=qi−1, we even have\(q_{i}/p_{i}\leq (1-\alpha_{i})/(\hat{\rho}-1)\).
Proof
By induction: The claim holds for i=0 since α0=0 by definition, γ0+β0=ρ−1 and thus Φ0=ρ−1. We assume the lemma holds up to i, and prove it for i+1 by case distinction on the way the height of rectangle qi+1 is determined. (For i=1, case 2 applies.)
Case 1:
qi+1=αipi.
By Lemma 4 we may assume βi=0. By (1), this further implies pi=(1−αi+1)pi+1. Hence
The online algorithm A is by assumption ρ-competitive after packing rectangle qi+1, which means that the distance between rectangles qi+1 and pi is not too large, i.e., αi+1pi+1≤γipi+(ρ−1)qi+1=γipi+(ρ−1)αipi. Together with Lemma 1 this gives
for \(\rho \le \hat{\rho}\). (This upper bound for αi+1, obtained by setting γi=0 and αi=ρ−1 (cf. Lemma 1) is rather weak, but sufficient for our purposes.)
Finally, by Lemma 3, the induction assumption and Lemma 1 we get
Case 2:
qi+1=βipi.
By Lemma 1 we have βi≤ρ−1 and thus,
(2)
which is less than \(1/(\hat{\rho}-1)\) for \(\rho \le \hat{\rho}\).
The online algorithm A is by assumption ρ-competitive after packing rectangle qi+1, which means that the distance between rectangles qi+1 and pi is not too large, i.e. αi+1pi+1≤γipi+(ρ−1)qi+1=γipi+(ρ−1)βipi. This, together with βi+γi≤ρ−1 (by Lemma 1) gives
for \(\rho \le \hat{\rho}\). (In the upper bound computation for αi above we assumed that γi is as large as possible and βi is as small as possible. This is justified by the fact that \(\frac{\rho-1}{\rho}<\frac{1}{\hat{\rho}-1}\).)
For the potential, Lemma 3 gives
(3)
which is strictly less than ρ−1 for ρ sufficiently close to \(\hat{\rho}\). (Again, for the last inequality in (3), note that increasing βi as much as possible instead of γi is justified: If we let \(f(\beta,\gamma)=\frac{\gamma+2(\rho-1)\beta -1}{1+\beta}\), then
To argue that \(\alpha_{i+1}\leq 1/(\hat{\rho}-1)\) we shift the concatenated rectangles qi,pi down as far as possible, i.e., until either γi=0 or αi=0 (thereby increasing αi+1). By shifting qi,pi down, the length of pi decreases, therefore γi can become 0. At the same time pi+1 increases, causing the optimal and online solution to increase by the same amount. So the online algorithm is still ρ-competitive after this shift.
If γi=0, then αi+1pi+1≤(ρ−1)qi+1=(ρ−1)qi≤pi. Thus \(\alpha_{i+1}\leq 1/2 \leq 1/(\hat{\rho}-1)\).
If αi=0, the rectangles pi−1,qi,pi are concatenated. To show \(\alpha_{i+1}\leq 1/(\hat{\rho}-1)\) for this case, we distinguish three subcases.
Case 3a:
qi+1=qi=αi−1pi−1.
By Lemma 4 we can assume βi−1=0 (and hence pi=pi−1). Thus we conclude that γipi=γi−1pi−1+(ρ−1)qi−pi≤γi−1pi−1. Thus (using Lemma 1 again),
and therefore
for \(\rho \le \hat{\rho}\).
Case 3b:
qi+1=qi=βi−1pi−1.
Since αi=0 and βi=0 we have Φi=γi≤(2(ρ−1)2−1)/ρ (cf. (3)). Thus,
The latter is increasing in ρ, so we conclude (after multiplying the enumerator and denominator with ρ) that
by definition of \(\hat{\rho}\). (Recall that \(3\hat{\rho}^{2}-9\hat{\rho}+4=0\).)
Case 3c:
qi+1=qi=qi−1. By Lemma 4 we may assume βi−1=0, so that actually qi−1,pi−1,qi,pi are concatenated and pi=pi−1. Since γipi=γi−1pi−1+(ρ−1)qi−pi<γi−1pi−1, i.e., the improvement of A upon ρ-competitiveness decreases, the value of αi+1 is smaller than αi could at most be, thus, in particular, less than \(1/(\hat{\rho}-1)\).
By Lemma 4 we can assume βi=0. Furthermore, Lemma 2 allows us to shift pi+1 resp. the concatenated qi+1pi+1 down until αi+1=βi+1=0 without affecting Φi+1 (although this might result in a negative value of γi+1 in case Φi+1 is negative). Summarizing, let us assume that qi,pi,qi+1,pi+1 are concatenated.
We seek to analyze how Φi and Φi+1 vary as the concatenated qi,pi,qi+1,pi+1 are shifted upward. By Lemma 2, Φi remains unchanged. As to Φi+1, observe that shifting qi,pi,qi+1,pi+1 upward by one unit will increase αipi and hence qi+1 as well as pi and pi+1 by one unit each. Hence A(Li+1) increases by 4. On the other hand, OPT(Li+1) increases by 2, so that γi+1pi+1 increases by (2ρ−4). Hence shifting qi,pi,qi+1,pi+1 upward will increase Φi+1 as long as Φi+1<2ρ−4. So we are led to distinguish the following two cases:
Φi+1>2ρ−4:
In this case, Φi+1 will increase as we shift qi,pi,qi+1,pi+1 downward. Doing so, we decrease qi+1. So we eventually end up in a situation where either qi+1=qi (which will be treated in Case 3 below) or γi becomes zero (revealing that Φi=−(ρ−2)α/(1−α) must be negative). But γi=0 implies
So Φi+1=γi+1=(ρ−1)αi−1<0, contradicting our assumption that Φi+1>2ρ−4.
Φi+1≤2ρ−4:
In this case Φi+1 increases as we shift qi,pi,qi+1,pi+1 upward until either qi gets tight in the sense that A(Li−pi)=ρOPT(Li−pi) or Φi+1=2ρ−4 is reached. The latter is impossible: Since γi+1pi+1=γipi+(ρ−1)qi+1−pi+1, we conclude (using Lemma 1) that
contradicting our assumption that Φi+1=2ρ−4.
Finally, assume that qi gets tight. In this case, γipi=ρ(pi−pi−1)−pi≥ραipi−pi. So γi≥ραi−1. Similarily, γi+1pi+1=γipi+(ρ−1)qi+1−pi+1. Dividing by pi+1=pi, we obtain γi+1=γi+(ρ−1)αi−1. Hence
The derivative with respect to γi of the above is 1/(1+βi)−1/(1−αi)≤0, so ΔΦ is decreasing in γi. Thus we may choose γi=0. Additionally, we have αi≤βi, otherwise we are not in this case. With γi=0 and under the constraints αi≤βi≤ρ−1,αi+βi≤ρ−1 we have
has partial derivative Δα=0 for β=ρ−2. Plugging this value into Δ, we find that the resulting Δ is independent of α and equals \(\rho -2-\frac{1}{\rho-1} < -0.1\). On the boundary α=0 the function Δ=Δ(β) is less than −0.04 for β∈[0,ρ−1] and on the boundary α=β the function Δ=Δ(β) is bounded from above by −0.2 for \(\beta \in [0,\frac{\rho-1}{2}]\). (Note that α=β implies \(\beta \le \frac{\rho-1}{2}\).) We omit the details.
Case 3:
qi+1=qi.
By definition of qi+1, we have αipi≤qi+1=qi. Thus, Lemma 5 implies \(\alpha_{i} \le q_{i}/p_{i} \le \frac{1-\alpha_{i}}{\hat{\rho}-1}\) or, equivalently, \(\alpha_{i} \le 1/\hat{\rho}\). Thus we conclude that
Now, as in Case 1, let us assume that βi=βi+1=0 and shift the concatenated qi+1pi+1 down until αi+1 becomes zero as well. This leaves Φi+1 (and, of course, also Φi) invariant, but may result in a negative value of γi+1 in case Φi+1 (=γi+1 after the shift) is negative. (As we are only interested in ΔΦ, we do not care about negative values of γi+1 here.) Thus assume that qi,pi,qi+1,pi+1 are concatenated.
We claim that shifting the concatenated qi,pi,qi+1,pi+1 down increases Φi+1 (while leaving Φi unchanged). Indeed moving down decreases both pi and pi+1 by one unit, so that in total A(Li+1) decreases by 3 units, while OPT(Li+1) decreases by only one unit. Thus γi+1pi+1 increases with 3−ρ units while pi+1 decreases with one unit. This shows that moving qi,pi,qi+1,pi+1 down increases Φi+1=γi+1 whenever Φi+1>ρ−3.
To show that Φ decreases, we may assume that Φi+1>ρ−3—else a significant decrease of at least \(\hat{\rho}-\rho\) follows already immediately from (4). But then, as we have seen above, we may also assume w.l.o.g. that qi,pi,qi+1,pi+1 is shifted down as far as possible, i.e., until αi=0. (Note that this may even result in a negative value of γi, but we do not care, as we are only interested in Φ-values.) When αi=0, however, then
is significantly negative since γi+1pi+1=γipi+(ρ−1)qi+1−pi+1, so that \(\gamma_{i+1} \le \gamma_{i} +\frac{\rho-1}{\hat{\rho}-1} -1\).
Summarizing, in each case there is a significant decrease in the potential function, provided that \(\rho < \hat{\rho}\). □
4 Conclusions
We have solved the (30 year old) problem of analysing Brown-Baker-Katseff sequences and provided an optimal online algorithm for these sequences. Up to now all previous lower bounds for online strip packing were based on Brown-Baker-Katseff sequences. A natural question to ask is whether (or to what extent) these sequences are worst case sequences for online strip packing. In Harren and Kern (2011) we have tried to analyze more generally sequences of “thin” items pi and “blocking” items qj, which are not necessarily alternating. We suceeded in proving lower and upper bounds close to 2.6 for such sequences. Determining the exact value appears to be involved, but in any case, our results show that to close the gap between the currently best lower bound of 2.6 and the currently best upper bound of 6.6, completely new ideas are needed.
Acknowledgement
Part of this research has been funded by the Dutch BSIK/BRICKS project.
Open Access
This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.