Improved Lower Bounds for Online Hypercube and Rectangle Packing
David Blitza , Sandy Heydrichb,1 , Rob van Steec , André van Vlietd , Gerhard J. Woegingere

arXiv:1607.01229v2 [cs.DS] 6 Nov 2017

b Max

a Robeco, Weena 850, 3014 DA Rotterdam, The Netherlands
Planck Institute for Informatics, Building E1.4, and Saarbrücken Graduate School of Computer Science, Building E1.3, Saarland
Informatics Campus, D-66123 Saarbrücken, Germany
c Department of Mathematics, Universität Siegen, Walter-Flex-Strasse 3, D-57068 Siegen, Germany
d Zwaluwlaan 18, 2261 BR Leidschendam, The Netherlands
e Department of Computer Science, RWTH Aachen, D-52056 Aachen, Germany

Abstract
Packing a given sequence of items into as few bins as possible in an online fashion is a widely studied problem. We
improve lower bounds for packing boxes into bins in two or more dimensions, both for general algorithms for squares
and rectangles (in two dimensions) and for an important subclass, so-called Harmonic-type algorithms for hypercubes
(in two or more dimensions). Lastly, we show that two adaptions of ideas from a one-dimensional packing algorithm
[1] to square packing do not help to break the barrier of 2.
Keywords: Bin packing, Hypercube packing, Online algorithm

1. Introduction
In this paper, we consider the problem of online bin packing in two or more dimensions. This problem is defined
as follows: We receive a sequence of boxes h1 , . . . , hn (called items) in d-dimensional space, and each item hi has size
si( j) in dimension j. We also consider the special case where all items are hypercubes with the same edge length si in
all dimensions. We furthermore have an infinite number of bins, which are hypercubes of edge length one. We have to
assign each item hi to a bin and a position (x1 , . . . , xd ) inside this bin, such that 0 ≤ x j ≤ 1− s(i j) for all 1 ≤ j ≤ d and no
two items in the same bin are overlapping. Items must be placed parallel to the axes of the bins and in the orientation
given in the input (i.e., rotations are not allowed). We call a bin used if at least one item is assigned to it, and our goal
is to minimize the number of used bins. The online setting requires us to assign an item to a bin immediately when it
arrives, without knowledge of future items. We consider this problem in two or more dimensions.
For measuring the quality of a solution of the algorithm, we use the standard notion of asymptotic performance
ratio. For an input sequence σ, let A(σ) be the number of bins algorithm A uses to pack the items in σ and let
OPT (σ) be the minimum number of bins in which these items can be packed. The asymptotic performance ratio for
A is defined as
(
)
A(σ)
R∞
=
lim
sup
sup
OPT
(σ)
=
n
A
OPT (σ)
n→∞
σ
If O denotes a class of packing algorithms, then the optimal asymptotic performance ratio for class O is defined as
R∞
= inf A∈O R∞
A . From now on, we will only talk about asymptotic performance ratios, although we omit the word
O
asymptotic.

Email addresses: d.c.blitz@robeco.nl (David Blitz), heydrich@mpi-inf.mpg.de (Sandy Heydrich), rob.vanstee@uni-siegen.de
(Rob van Stee), andrevanvliet@xs4all.nl (André van Vliet), woeginger@algo.rwth-aachen.de (Gerhard J. Woeginger)
1 Sandy Heydrich is supported by a Google Europe PhD Fellowship.

1

1.1. Previous Results
The classic online bin packing problem in one dimension was first considered by Ullman [2], and he also gave
the FirstFit algorithm with performance ratio 17
10 [3]. The NextFit algorithm was introduced by Johnson [4], who
showed that this algorithm has a performance ratio of 2.
The Harmonic algorithm was introduced by Lee and Lee [5]. If we define u1 = 2, ui+1 = ui (ui − 1) + 1, then
P
1
this algorithm has performance ratio h∞ = ∞
i=1 ui −1 < 1.69104. It uses bounded space (i.e. only a constant number
of bins are open at a time, meaning that items can be added to them) and they showed that no algorithm with this
property can perform better. Later, various improvements of this approach were given (using unbounded space),
373
< 1.63597) [5], ModifiedHarmonic (performance ratio < 1.61562)
including RefinedHarmonic (performance ratio 228
and ModifiedHarmonic2 (performance ratio < 1.61217) by Ramanan et al. [6], Harmonic++ (performance ratio
< 1.58889) by Seiden [7], and finally SonOfHarmonic (performance ratio 1.5816) by Heydrich and van Stee [1]. Very
recently, the bound has further been improved to 1.5783 by the algorithm AdvancedHarmonic [8]. The best general
lower bound of 1.54037 for online bin packing in one dimension was given by Balogh et al. [9].
Online bin packing of rectangles was first discussed by Coppersmith and Raghavan [10]. They gave an algorithm
43
which has in two dimensions a performance ratio of 13
4 for general rectangles and 16 for squares. Additionally, they
showed a lower bound of 43 for square packing in any dimension d ≥ 2. Csirik and van Vliet improved upon this by
giving an algorithm that achieves hd∞ performance ratio for any dimension d ≥ 2 [11]. They also show that this is a
lower bound for bounded space algorithms, although their algorithm uses unbounded space. Later, Epstein and van
Stee provided a bounded space algorithm that matches this lower bound [12]. In the same paper, they also give an
optimal online bounded space algorithm for box packing (i.e. items are not hypercubes anymore but can have different
sizes in different dimensions), although they do not provide the exact performance ratio. Finally, Han et al. [13] gave
an upper bound of 2.5545 for the special case of d = 2, which is the best bound currently known.
The best known lower bounds for hypercube packing are 1.6406 for two dimensions and 1.6680 for three dimensions [14]. For box packing, the best known lower bounds are 1.851 for two dimensions and 2.043 for three
dimensions [15]. Regarding upper bounds, the best algorithm for square packing achieves a performance ratio of
2.1187 and the best algorithm for cube packing achieves 2.6161 [16]. For rectangle packing, a 2.5545-competitive
algorithm is known, as well as a 4.3198-competitive algorithm for online three dimensional box packing [13].
1.2. Our Contribution
We improve the general lower bound for square packing in two dimensions to 1.680783. In the upcoming WAOA
2017, Epstein et al. improved this lower bound further to 1.75, using different methods [17]. For rectangle packing, we
improve the general lower bound to 1.859. Furthermore, we improve the lower bound for Harmonic-type algorithms
for hypercube packing in any dimension d ≥ 2. This uses a generalization of the method of Ramanan et al. [6]. In
particular, we show that such an algorithm cannot break the barrier of 2 for d = 2, by giving a lower bound of 2.02
for this case. This shows that substantially new ideas will be needed in order to improve significantly on the current
best upper bound of 2.1187 and get close to the general lower bound. Our lower bound tends to 3 for large numbers
of dimensions.
Lastly, we also show that even when incorporating two central ideas from the currently best one-dimensional
bin packing algorithm [1] into two-dimensional square packing, similar lower bounds as those for Harmonic-type
algorithms can still be achieved.
1.3. Preliminaries
At several points in this paper, we use the notion of anchor points as defined by Epstein and van Stee [18]. We
assign the coordinate (0, . . . , 0) to one corner of the bin, all edges connected to this corner are along a positive axis
and have length 1. Placing an item at an anchor point means placing this item parallel to the axes such that one of its
corners coincides with the anchor point and no point inside the item has a smaller coordinate than the corresponding
coordinate of the anchor point. We call an anchor point blocked for type s items in a certain packing (i.e. in a bin that
contains some items), if we cannot place an item of type s at that anchor point (without overlapping other items).

2

2. Lower Bound for General Algorithms for Square Packing
2.1. Van Vliet’s Method
For deriving a general lower bound on the performance ratio of online hypercube packing algorithms, we extend
an approach by van Vliet [15] based on linear programming. Problem instances considered in this approach are
characterized by a list of items L = L1 . . . Lk for some k ≥ 2, where each sublist L j contains α j · n items of side length
s j (we will also call such items “items of size s j ” or simply “s j -items”). We assume s1 ≤ . . . ≤ sk . The input might
stop after some sublist. An online algorithm A does not know beforehand at which point the input sequence stops,
and hence the asymptotic performance ratio can be lower bounded by
R ≥ min max lim sup
A

j=1,...,k

n→∞

A(L1 , . . . , L j )
OPT (L1 , . . . , L j )

For this approach, we define the notion of a pattern: A pattern is a multiset of items that fits in one bin. We denote
a pattern by a tuple (p1 , . . . , pk ), where pi denotes the number of si -items contained in the pattern (possibly zero). We
call a pattern p dominant if the multiset consisting of the items of p and an additional item of the smallest item size
that is used by p cannot be packed in one bin. The performance of an online algorithm on the problem instances we
consider can be characterized by the number of bins it packs according to a certain pattern. Van Vliet denotes the set
of all feasible patterns by T , which is the union of the disjoint sets T 1 , . . . , T k where T j contains patterns whose first
non-zero component is j (i.e., whose smallest item size used is s j ). We can then calculate the cost of an algorithm A
Pj P
by A(L1 , . . . , L j ) = i=1
p∈T i n(p), where n(p) denotes the number of bins A packs according to pattern p. Note that
we only need to consider dominant patterns in the LP [15]. As the variables n(p) characterize algorithm A, optimizing
over these variables allows us to minimize the performance ratio over all online algorithms with the following LP:
minimize
subject to

R
X

p j · x(p)
p∈T
j X
X

≥ αj

1≤ j≤k

x(p) ≤ lim

i=1 p∈T i

n→∞

x(p) ≥ 0

OPT (L1 , . . . , L j )
R 1≤ j≤k
n
∀p ∈ T

In this LP, the variables x(p) replace n(p)/n, as we are only interested in results for n → ∞. Note that item sizes
are always given in nondecreasing order to the algorithm. In this paper, however, we will often consider item sizes in
nonincreasing order for constructing the input sequence and generating all patterns.
2.2. Proving a lower bound of 1.680783
In this section, we will prove the following theorem:
Theorem 1. No online algorithm can achieve a competitive ratio of 1.680783 for the online square packing problem.
OPT (L ...L )

1
j
Consider the input sequence in Table 1. First of all, we need to prove the correctness of the values
n
for j = 1, . . . , k and n → ∞. To prove a lower bound, we do not need to prove optimality of the offline packings
that we use. It is sufficient to prove feasibility. To do this, we use anchor packings. An anchor packing is a packing
where every item is placed at an anchor point. In this section, we use 4202 anchor points. The anchor points are at the
positions for which both coordinates are integer multiples of (1 + )/420. Note that every item used in the construction
apart from the ones in L1 have sides which are exact multiples of (1 + )/420. Therefore, whenever we place an item
at an anchor point, and the item is completely contained within the bin, it will fill exactly a square bounded by anchor
points on all sides.
To check whether a given pattern is feasible, the items of size s1 can be considered separately. Having placed all
other items at anchor points, we can place exactly one item of size s1 at each anchor point which is still available.
Here an anchor point (x, y) is available if no item covers the point (x + , y + ). By the above, after all other items
have been placed at anchor points, it is trivial to calculate the number of available anchor points; at least all the anchor
points with at least one coordinate equal to (1 + )419/420 are still available.

3

sublist Li
L1
L2
L3
L4
L5
L6
L7
L8
L9
L10

number of items αi
839n
10n
8n
4n
39n
8n
4n
7n
5n
n

item size si
1/420 − 
1/105 + /105
1/84 + /84
1/42 + /42
1/21 + /21
1/20 + /20
1/10 + /10
1/5 + /5
1/4 + /4
1/2 + /2

OPT (L1 . . . Li ) · 176400/n
839
999
1199
1599
17199
20727
27783
77175
132300
176400

Table 1: The input sequence that gives a lower bound of 1.680783 together with optimal solutions.

For any pattern that we use, the largest items in it are always arranged in a square grid at the left bottom corner of
the bin (at anchor points). The second largest items are arranged in an L-shape around that square. It is straightforward
to calculate the numbers of these items as well. The patterns used for the given upper bounds on the optimal solution
are listed in Table 2. Note that not all of these patterns are greedy (in the sense that we add, from larger to smaller
items, always as many items of the current type as still fit).
Let us give some intuition on how these patterns are constructed. We start by finding a pattern that contains the
maximal number of the largest type of items, and then add greedily as many items as possible of the second largest
type, then third largest type and so on. We take as many bins with this pattern as are necessary to pack all the largest
items; a certain number of items of all other types remain. We continue by choosing the pattern that contains the
largest possible number of items of the second-largest type and fill it up greedily as before with other items. We use
this pattern in such a number of bins that all remaining items of the second-largest type are packed. We continue like
that until all items are packed. You can see this approach for example in the patterns used for OPT (L1 . . . L3 ). We can
pack 6889 items of size s3 into one bin. With these, we can pack no more than 207 s2 -items, and finally we can add at
most 863 s1 -items; this gives the first pattern. We need n · 8/6889 bins with this pattern to pack the 8n s3 -items. This
leaves n · 67234/6889 items of size s2 unpacked, and as we can pack at most 10816 s2 -items into one bin (and 3344
s1 -items with them), this gives a certain amount of bins with this second pattern (3344, 10816, 0, . . . , 0).
However, we sometimes slightly derive from this construction, e.g., in the patterns used for OPT (L1 . . . L5 ). In a
bin with 400 items of size s5 , we could fit 81 items of size s4 . However, if we do so, we would pack more s4 -items
than necessary and thus lose space that we need in order to pack other items. In that case, we reduce the number of
s4 -items as much as possible while still packing all of them (in this case, we reduce it to 42).
In Figure 1, we give the optimal packing for the whole input sequence (i.e., for L1 . . . L10 ).
In order to prove lower bounds, we will use the dual of the LP given above. It is defined as follows:
maximize
subject to

Pk
j=1
k
X

α jλ j

λi pi +

i= j

−

k
X

µi ≤ 0

∀p ∈ T j , 1 ≤ j ≤ k

i= j

k
X
j=1

OPT (L1 . . . L j )
≤1
n→∞
n

µ j · lim

λj ≥ 0
µj ≤ 0

1≤ j≤k
1≤ j≤k

Note that any feasible solution to this dual gives us a valid lower bound for the problem. In Table 3, we specify a solution and then prove that it is indeed feasible for the dual LP. In this table, the constant x is defined as
4410/338989303.

4

s6
s6
s6
s6

s1
s2
s2
s2
s2
s2

s3
s3
s3
s3

s4

···
s5

s4

s6

s7

s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5 s5
s5
s7
s5
s8 -item
s8 -item
s8 -item
s8 -item s
5
s7
s5
s5
s5
s8 -item s5
s9 -item
s9 -item
s9 -item
s5
s5
s5
s8 -item s5
s5
s9 -item
s5
s5
s10 -item
s8 -item s5
s5
s5
s9 -item
s7
s7 s5
s5
s6 s6 s6 s6

Figure 1: How to pack the whole input sequence L1 . . . L10 . Note that these sketches are not true to scale for the sake of readability.

i
1
2
3

4
5
6
7
8
9
10

s1
176400
3344
176400
863
3344
176400
863
863
3344
176400
10477
839
10493
839
839
10541
1918
839
1918
839

s2
0
10816
0
207
10816
0
207
207
10816
0
103
16
102
16
16
99
23
10
23
10

patterns used for OPT (L1 . . . Li )/n
s3
s4
s5
s6
s7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6889
0
0
0
0
0
0
0
0
0
0
0
0
0
0
165 1681
0
0
0
6889
0
0
0
0
0
0
0
0
0
0
0
0
0
0
83
42
400
0
0
8
4
39 361 0
83
42
400
0
0
8
4
39
37 81
8
4
39 361 0
83
42
400
0
0
18
10
90
19 10
8
4
39
8
4
19
10
90
19 10
8
4
39
8
4

s8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
16
7
16
7

s9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
5

s10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1

Table 2: Patterns used for the optimal solutions.

5

number of bins with this pattern
divided by n
839/176400
10/10816
31393/6624800
8/6889
33617/37255712
1944236893/410744224800
4/1681
12788/11580409
31961/37255712
646638631/136914741600
39/400
8/361
13767/144400
4/81
500/29241
13143/144400
7/16
5/9
7/36
1

i
λi /x
−µi /x

1
1
863

2
16
3312

3
25
4125

4
100
8100

5
400
15600

6
400
14800

7
1600
27200

8
6400
44800

9
6400
32000

10
25600
25600

Table 3: The variable values for the dual solution. Here, x = 4410/338989303.

Note that the dual constraint
−

k
X
j=1

µ j · lim

n→∞

OPT (L1 . . . L j )
≤1
n

is satisfied with equality.
It thus remains to check the other constraints, where we have one constraint for every pattern. For verifying that
P
P
all constraints ki= j λi pi + ki= j µi ≤ 0 are satisfied, we see that it suffices to check that for every j = 1, . . . , k the
Pk
P
inequality max p∈T j i= j λi pi ≤ − ki= j µi holds. We can interpret the λi values as weights assigned to items of type i,
and thus the problem reduces to finding the pattern in T j with maximum weight – a knapsack problem. The µi -values
define the capacity of the knapsack. In order to solve this efficiently, we introduce a dominance notion for items.
Definition 1. We say that m2 items of size si dominate an item of size s j , denoted by m2 si  s j , if msi ≤ s j and
m2 λi ≥ λ j .
In the case that m2 si -items dominate an s j -item, we can replace one item of size s j by m2 items of size si (arranged
in an m × m grid), as the items to do not take more space. Furthermore, the weight of the pattern only increases by this
replacement step, so it suffices to only examine the pattern without s j items. Note that the -operator is transitive.
For our input, we use the following dominance relations:
42 s1  s2

52 s1  s3

22 s3  s4

22 s4  s5

s5  s6

22 s6  s7

22 s7  s8

s8  s9

22 s9  s10

It is easy to check that these are indeed fulfilled by the λi -values given above. The dominance relations give us
that whenever a pattern contains s1 -items, we can replace all other items in this pattern by s1 -items as well – thus,
for set T 1 , we only need to consider the pattern that contains only s1 -items (and the maximal number of them, i.e.,
176400 such items). So using the dominance relation, we have reduced the number of patterns dramatically. Similarly,
for T 3 , . . . , T 10 , we only have to consider one pattern each. Only for T 2 , we have to be careful: As s3 -items are not
dominated by s2 items, we also have to consider patterns that contain s2 and s3 -items. The following Lemma will
show that the pattern that contains 6889 s3 -items and 207 s2 -items is the maximum weight pattern for this case.
Lemma 1. Among all patterns that only contain items of sizes s2 and s3 , the pattern with 6889 s3 -items and 207
s2 -items has the highest weight given the λi -values of Table 3.
Proof. Let p∗ be the pattern under consideration. We note that

λ2
(1/105)2

λ3
, i.e., the weight per area is larger for
(1/84)2
2
104
105 · (1 + ) . Note that no pattern with these

<


the s3 -items than for the s2 -items. Furthermore, p∗ occupies an area of
two item types can cover a larger area. Hence, no pattern can achieve a larger weight.

In Table 4, we list all patterns that need to be checked, together with their weight and the knapsack capacity.
Finally, in order to determine the lower bound proven by this input, we compute 839λ1 + 10λ2 + 8λ3 + 4λ4 + 39λ5 +
8λ6 + 4λ7 + 7λ8 + 5λ9 + λ10 = 569767590/338989303 > 1.680783. This concludes the proof of Theorem 1.
3. Lower Bounds for General Algorithms for Rectangle Packing
In this section, we present a lower bound on the more general two-dimensional bin packing, where items are
allowed to be arbitrary rectangles and not necessarily squares. In this setting, we receive a sequence of n items, where
6

j
1
2
3
4
5
6
7
8
9
10

heaviest pattern p from T j
176400 × s1
207 × s2 , 6889 × s3
6889 × s3
1681 × s4
400 × s5
361 × s6
81 × s7
16 × s8
9 × s9
1 × s10

w(p)/x
176400
175537
172225
168100
160000
144400
129600
102400
57600
25600

knapsack capacity: (
176400
175537
172225
168100
160000
144400
129600
102400
57600
25600

P10
i= j

−µi )/x

Table 4: The patterns that have to be considered to verify the first set of constraints in the dual LP. Again, x = 4410/338989303.

j
1
2
3

Level 1
wj
hj
1/4 − 300δ
1/4 + 100δ 1/6 − 2
1/2 + 200δ

j
4
5
6

Level 2
wj
hj
1/4 − 30δ
1/4 + 10δ 1/3 + 
1/2 + 20δ

j
1
2
3

Level 3
wj
hj
1/4 − 3δ
1/4 + δ 1/2 + 
1/2 + 2δ

Table 5: The input sequence for the 1.859 lower bound. The tables show the items for the first, second and third level.  and δ are assumed to be
sufficiently small positive constants.

the i-th item has width wi and height hi . The bins are still squares of side length one, and we are not allowed to rotate
the items. Note that the LP and its dual are still the same, however, we need to adapt our definition of item dominance
as follows.
Definition 2. We say that m1 × m2 items of size si dominate an item of size s j , denoted by (m1 × m2 )si  s j , if
m1 wi ≤ w j , m2 hi ≤ h j and m1 m2 λi ≥ λ j . Instead of (1 × 1)si  s j , we will simply write si  s j .
Again, this means that we can replace one item of size s j by m1 m2 items of size si which are arranged in an
m1 × m2 -grid, while only increasing the weight (sum of λ-values) of the pattern.
3.1. A lower bound of 1.859 using nine item types
The construction for our lower bound relies on nine item types that are arranged in 3 groups, also called levels.
Corresponding to these item types, we have nine lists L1 , . . . , L9 , where each L j consists of n items of size s j . The
item sizes are given in Table 5.
First of all, we will again give the values for OPT (L1 . . . L j ) in Table 6. The packings for the optimal solution are
depicted in Figure 2.
We will now give an optimal solution for the primal LP and then verify its feasibility by checking the constraints,
and verify its optimality by giving a matching dual solution and a proof of its feasibility. The optimal primal solution
uses 15 different patterns as listed in Table 7. The packings for some of these (where it is not that easy to see how to
pack the pattern) are depicted in Figure 3.
To verify feasibility of this solution, note that all the constraints hold with equality (except for the non-negativity
constraints of course) if we set R = 768/413 > 1.859. For proving optimality, we use the dual solution given in Table
j
OPT (L1 . . . L j )/n

1
1/24

2
1/12

3
1/6

4
1/4

5
1/3

6
1/2

7
5/8

Table 6: The optimal solution values for the 1.859 lower bound.

7

8
3/4

9
1

1

1

1

1

1

1

2

2

1

2

3

1

1

1

1

1

1

2

2

1

2

3

1

1

1

1

1

1

2

2

1

2

3

1

1

1

1

1

1

2

2

1

2

3

1

1

1

1

1

1

2

2

1

2

3

2

1

2

3

1

1

1

1

1

1

(a) OPT (L1 )

2

(b) OPT (L1 L2 )

(c) OPT (L1 L2 L3 )

1

2

3

1

2

3

1

2

3

1

2

3

1

2

3

1

2

3

1

2

3

1

2

3

1

2

3

1

2

3

1

2

3

4
1

2

4

4

4

4

4

1

2

3

1

2

3

4

5

6

4

5

6

4

4

(f) OPT (L1 . . . L6 )

1

2

3

4

5

6

8

5

5

(e) OPT (L1 . . . L5 ): We have n/4 bins with the left packing
and n/12 bins with the right packing
1

2

3

4

5

6

7

7

5

3

(d) OPT (L1 . . . L4 )

7

5

7

7

1

2

3

1

2

3

4

5

6

4

5

6

7

(g) OPT (L1 . . . L7 ): We have n/4 bins with the left packing
and 3/8 · n bins with the right packing
1

2

3

1

2

3

4

5

6

4

5

6

8

(h) OPT (L1 . . . L8 ): We have n/2 bins with the left packing
and n/4 bins with the right packing

1

2

3

4

5

6

7

8

9

(i) OPT (L1 . . . L9 )

Figure 2: Optimal solutions for sublists L1 . . . L j for all j = 1, . . . , 9. The number within every item denotes its type.

8

pattern p
p(1)
p(2)
p(3)
p(4)
p(5)
p(6)
p(7)
p(8)
p(9)
p(10)
p(11)
p(12)
p(13)
p(14)
p(15)
p(16)
p(17)

p1
24
12
12
-

p2
12
6
2
2
-

p3
6
6
2
2
4
-

p4
4
4
2
8
2
1
-

p5
4
4
2
1
1
1
1
-

p6
2
2
1
1
1
1
2
-

p7
4
2
4
1
1
1
-

p8
2
1
1
1
1
-

type

p9
1
1
1
1

T1

T2
T3
T4

T5
T6
T7
T8
T9

x(p)
29/4956
289/4956
11/826
15/413
17/1239
34/1239
64/413
55/1239
74/1239
21/413
32/413
3/413
29/413
128/413
96/413
96/413
192/413

Table 7: The optimal primal solution for the 1.859 lower bound. The table gives the patterns, the set T j they belong to, and the value of the LP
variable x(p) for each pattern.

3
4

4

6

5
3

4

4

6

2

3

5

4

4

5

6

3
(a) p(6)

8

3
5

2

6
7

3
(b) p(7)

(c) p(14)

Figure 3: Packings of some of the patterns of the optimal LP solution. The number within each item denotes its type.

9

j
1

types to consider
1

2

2, 4

3
4
5

3, 4
4
5,7

6

6,7

7
8
9

7
8
9

heaviest patterns p from T j
24 × s1
18 × s2
6 × s2 , 8 × s4
12 × s2 , 4 × s4
4 × s3 , 6 × s4
8 × s4
3 × s5 , 4 × s7
2 × s6 , 2 × s7
1 × s6 , 4 × s7
4 × s7
3 × s8
1 × s9

w(p) · 413
1152

(

P9
i= j

−µi ) · 413
1152

864

864

816
576
504

816
576
504

432

432

288
216
144

288
216
144

Table 8: The patterns that need to be considered for verifying the feasibility of the dual solution, together with their weight and the knapsack
capacity.

9. In order to verify its feasibility, note that the dual LP constraint
−

k
X

µ j · lim

n→∞

j=1

OPT (L1 . . . L j )
≤1
n

is satisfied with equality. It remains to check the other dual constraints, where again we have to test whether
P
P
max p∈T j ki= j λi pi ≤ − ki= j µi for all j = 1, . . . , k. For solving the associated knapsack problem, we use the following
dominance relations to simplify our task:
s1  s2
s4  s5
s7  s8

(2 × 1)s2  s3
(2 × 1)s5  s6
(2 × 1)s8  s9

(1 × 2)s1  s4
s4  s7

We list the optimal patterns to be considered for the knapsack problem in Table 8. In the following lemmas, we will
prove that it suffices to consider these patterns.
Lemma 2. For T 2 , the patterns p(1) = (0, 6, 0, 8, 0, . . . , 0), p(2) = (0, 12, 0, 4, 0, . . . , 0), and p(3) = (0, 18, 0, . . . , 0)
P
maximize w(p) = ki=2 λi pi , given the λi -values from Table 9.
Proof. In this proof, we abbreviate patterns by listing only their second and fourth components. Any vertical line
through a bin can intersect with at most two type 4 items, and any horizontal line with at most four. By arranging the
items in two rows of four, we see that (0, 8) is a dominent pattern. There are only two options for a horizontal line in
a bin that contains only type 2 and type 4 items:
• it crosses (at most) four type 4 items
• it crosses at most three items (of any type).
It is easy to see that (0, 8) is a (dominant) pattern: we can have two rows of four items. In general, if a bin contains eight
type 4 items, there is at least a height of 1/3 − 2ε where horizontal lines cross with at most three items (this height can
be more if the type 4 items are not exactly aligned). This in turn implies that a volume of at least (1/3−2ε)(1/4−300δ)
must remain empty in any bin that contains eight type 4 items, as the maximum total width of a set of three items is
3/4 + 300δ. It follows immediately that (6, 8) is a dominant pattern, as the free space in the packing tends to exactly
1/3 × 1/4 if ε → 0 and δ → 0 (and since it is indeed a pattern).
If there is a total height of more than 1/3 + ε at which a horizontal line intersects with four items, then by
considering the highest and the lowest such line, we can identify eight distinct type 4 items. Therefore, in a bin with
four to seven type 4 items, at a height of at least 2/3 − ε, a horizontal line intersects with at most three items, since you
10

3
4
3
3
4
3

4

4

4

4

Figure 4: A feasible packing for pattern p from Lemma 3

can only have one row of four type 4 items. Therefore, in such a bin, there must be (2/3 − ε)(1/4 − 300δ) of empty
816 840 864
space. We find the following patterns: (6, 7), (8, 6), (10, 5), (12, 4) with weights 792
413 , 413 , 413 , 413 , respectively.
If there are at most three type 4 items, then any horizontal line intersects with at most three items, the empty space
816 840 864
is at least 1/4 − 300δ, and the patterns are (12, 3), (14, 2), (16, 1), (18, 0) with weights 792
413 , 413 , 413 , 413 , respectively.
Lemma 3. For T 3 , the pattern p = (0, 0, 4, 6, 0, . . . , 0) maximizes w(p) =

Pk
i=2

λi pi , given the λi -values from Table 9.

Proof. In this proof, we again abbreviate patterns by listing only their third and fourth components. First of all, see
Figure 4 for a feasible packing of p. Horizontal lines can only intersect with these sets of items:
• three or four type 4 items
• at most two items which have total width at most 3/4 + 170δ
As above, (0, 8) is a dominant pattern. There is at least a height of 1/3 − 2ε at which horizontal lines intersect with at
most two items. There is at most a height of 1/3 − 2ε at which horizontal lines intersect with at most one type 4 item.
Since two type 3 items cannot be placed next to each other, this implies that (2, 8) is a (dominant) pattern, but with
768
.
a smaller weight of 413
If there are seven type 4 items, again there is at most a height of 1/3 − 2ε at which horizontal lines intersect with
at most one type 4 item, so (3, 7) is not a pattern. If there are four to six type 4 items, there is an empty volume of at
least (2/3 − ε)(1/4 − 170δ), so (4, 6) is dominant. Moreover, there is at least a height of 2/3 − ε at which horizontal
lines intersect with at most two items, so (5, 5) and (5, 4) are not patterns.
If there are three type 4 items, the empty volume is at least 1/4 − 170δ, so (6, 3) is a dominant pattern with weight
792
.
413 Finally, no bin can contain more than six type 3 items, so no other pattern can be heavier.
Lemma 4. For T 5 , the pattern p = (0, 0, 0, 0, 3, 0, 4, 0, 0) maximizes w(p) =
9.

Pk
i=2

λi pi , given the λi -values from Table

Proof. Note that λ5 = λ7 . Therefore the only question here is how many items of these types can be packed together
in a bin. No more than four type 7 items can be packed in any bin, and at most three type 5 items can be packed with
them (using similar arguments as above). Moreover, no more than six type 5 items can be packed in any bin, and if
there are less than four type 7 items in any bin, then any horizontal line in such a bin intersects with at most three
items. Thus at most seven items can be packed into any such bin.
Lemma 5. For T 6 , the patterns p(1) = (0, 0, 0, 0, 0, 2, 2, 0, 0) and p(2) = (0, 0, 0, 0, 0, 1, 4, 0, 0) maximize w(p) =
Pk
i=2 λi pi , given the λi -values from Table 9.
Proof. For a packing of p(1) , see Figure 3c. Observe that a bin can never contain more than two s6 -items, and together
with the fact that it is easy to see that no more than two s7 -items can be added to them, it follows that p(1) is a candidate
for the heaviest pattern. Likewise, it is clear that no bin can contain more than four s7 -items, and it is easy to see that
no more than one s6 -item can be added to those.
11

j
λ j · 413
−µ j · 413

1
48
288

2
48
48

3
96
240

4
72
72

5
72
72

6
144
144

7
72
72

8
72
72

9
144
144

Table 9: Dual solution for the 1.859 lower bound.

4. Lower Bound for Harmonic-Type Algorithms
Now, we consider the hypercube packing problem in d dimensions, for any d ≥ 2. We define the class C (h) of
Harmonic-type algorithms analogous to [6]. An algorithm A in C (h) for any h ≥ 1 distinguishes, possibly among
others, the following disjoint subintervals

• I 1 = (1 − y1 , 1

i
• I1, j = 1 − y j+1 , 1 − y j , for every j ∈ {1, . . . , h}

• I 2 = (yh , 1/2

i
• I2, j = yh− j , yh− j+1 , for every j ∈ {1, . . . , h}
• Iλ = (0, λ]
for some parameters y j and λ, where 1/3 = y0 < y1 < . . . < yh < yh+1 = 1/2 and 0 < λ ≤ 1/3. For convenience, we
assume that all y j are rational.
Algorithm A has to follow the following rules:
1. For each j ∈ {1, . . . , h}, there is a constant m j s.t. a 1/m j -fraction of the items of side length in I2, j is packed
2d − 1 per bin (“red items”), the rest are packed 2d per bin (“blue items”).
2. No bin contains an item of side length in I1,i and an item of side length in I2, j if i + j ≤ h.
3. No bin contains an item of side length in I 1 and an item of side length in I2, j .
4. No bin contains an item of side length in I1, j and an item of side length in I 2 .
5. No bin that contains an item of side length in Iλ contains an item of side length in I1, j , I2, j , I 1 or I 2 .
We will now define 2h + 1 input instances for the hypercube packing problem in d dimensions, and for each
instance we derive a lower bound on the number of bins any C (h) -algorithm must use to pack this input.
Every such input instance consists of three types of items. The input will contain N items of side length u, followed
by (2d − 1)N items of side length v and finally followed by MN items of side length t, where u, v, t and M will be
defined for each instance differently. We will then show, for every instance, that one u-item, 2d − 1 v-items and M
t-items can be packed together in one bin, thus the optimal packing for this input uses at most N bins.
4.1. Instances 1, . . . , h
Let  > 0 be arbitrarily small. For every j ∈ {1, . . . , h}, we define the following instance of the problem: Let
(1+)yh− j
K
u = 1+
for some large integer K such that t ∈ Iλ and yh−
∈ N. Clearly, u ∈ I1,h and
2 , v = (1 + )yh− j and t =
2K
j
v ∈ I2, j .
In order to show that one u-item, 2d − 1 v-items and M t-items can be packed in one bin, we will define anchor
points for each size and then place items at some of these such that no two items are overlapping.
There is only one anchor point for u-items, namely (0, . . . , 0), i.e. the origin of the bin. We place one u item
there. For items of side length v, we define anchor points as all points having all coordinates equal to (1 + )/2 or
(1 + )/2 − (1 + )yh− j . This defines 2d anchor points, but an anchor point can only be used for a v-item if at least one
coordinate is (1 + )/2. Hence, we can pack 2d − 1 v-items together with the u-item placed before.
(1+)y
− 2,
For items of side length t, the anchor points are all points with coordinates equal to i 2K h− j for i = 0, . . . , y2K
h− j
i.e. we have ( y2K
− 1)d anchor points for these items. These anchor points form a superset of all previous anchor points
h− j
for u- and v-items. Together with the fact that t divides u and v, we can conclude that all larger items take away an
12


d
integer amount of anchor points for the t-items. To be precise, the u-item blocks (u/t)d = K/yh− j anchor points for

d  d
 d
2K−y
K
−
t-items and each v-item blocks vt = (2K)d anchor points for t-items. Hence, we can add M := yh− jh− j − yh−
j
(2d − 1)(2K)d t-items to the items packed before.
A Harmonic-type algorithm A packs a 1/m j -fraction of the N(2d − 1) v-items 2d − 1 per bin, using

(2d −1)N/m j
= mNj
2d −1
d
− 1/m j ) 2 2−1
=
d

bins in total. The remaining N(2d − 1)(1 − 1/m j ) v-items are packed 2d per bin, adding another N(1


N(1 − 1/m j ) 1 − 21d bins.
N/m j of the u-items are added to bins with red v-items, the remaining N(1 − 1/m j ) items of side length u must be
packed one per bin.

d
2K−y
Finally, an algorithm in the class C (h) needs at least N M/ yh− jh− j bins to pack the t-items, giving


N 1 −

K
2K − yh− j

!d

2Kyh− j
− (2 − 1)
2K − yh− j
d

!d 





bins for these items. If we let K → ∞, this tends to N 1 − 1/2d − (2d − 1)ydh− j .
So, the total number of bins needed is at least
!
!
!
1
1
1
1
1
N
+ 1−
1− d +1−
+ 1 − d − (2d − 1)ydh− j
mj
mj
mj
2
2
!
!
!
1
1
1
= N 2+ 1−
1 − d − d − (2d − 1)ydh− j
mj
2
2
As the optimal solution uses at most N bins, the performance ratio of any such algorithm A must be at least
RA ≥ 2 + (1 − 1/m j )(1 − 1/2d ) − 1/2d − (2d − 1)ydh− j

j = 1, . . . , h

(1)

4.2. Instances h + 1, . . . , 2h
Another set of instances is given for any j ∈ {1, . . . , h}, if we use u = (1 + )(1 − yh− j+1 ), v = (1 + )yh− j and
(1+)yh− j (1−yh− j+1 )
K
t =
for some large enough integer K such that u ∈ I1,h− j , v ∈ I2, j , t ∈ Iλ and yh−
, K
∈ N. For
K
j 1−yh− j+1
these item sizes, the algorithm is not allowed to combine u-items with v-items in the same bin, although space for
items in I1,i with i > h − j is reserved in red bins containing v-items. We define the following anchor points: the
point (0, 0) for type u; all points with all coordinates equal to (1 + )(1 − yh− j+1 ) or (1 + )(1 − yh− j+1 ) − (1 + )yh− j
(1+)yh− j (1−yh− j+1 )
K
for type v; and all points with all coordinates equal to i
for some i ∈ {0, . . . , yh− j (1−y
− 2} for type
K
h− j+1 )
t. Again the anchor points for u- and v-items are a subset of the anchor points for t-items, and hence with the
same argumentation as before we can pack one u-item together with 2d − 1 v-items and M t-items if we choose
d  d

d
 d

K−y j (1−yh− j+1 )
K
K
K
d
M = yh−h−j (1−y
−
−
(2
−
1)
,
as
the
u-item
takes
up
anchor points of the t-items and each
)
y
1−y
yh− j
h− j+1
h− j
h− j+1

d
v-item takes up 1−yKh− j+1 of these anchor points.
A similar calculation to before can be done: An algorithm in class C (h) needs N/m j + N(1 − 1/m j )(1 − 1/2d ) bins
for red and blue items of type v. It needs N bins for u-items, as they are packed one per bin, and finally
NM


K−yh− j (1−yh− j+1 )
yh− j (1−yh− j+1 )

d

!d
!d 

Kyh− j
K(1 − yh− j+1 )
d

− (2 − 1)
K − yh− j (1 − yh− j+1 )
K − yh− j (1 − yh− j+1 ) 



d
K→∞
−−−−→ N 1 − 1 − yh− j+1 − (2d − 1)ydh− j



= N 1 −

13

bins are required to pack the t-items. Hence, we need at least
!
!
!

d
1
1
1
d
d
N
+ 1−
1 − d + 1 + 1 − 1 − yh− j+1 − (2 − 1)yh− j
mj
mj
2
! 
!
!
d
1
1
1
d
d
= N 2+
+ 1−
1 − d − 1 − yh− j+1 − (2 − 1)yh− j
mj
mj
2
bins in total. This gives the following lower bound for the performance ratio:


 
d
RA ≥ 2 + 1/m j + 1 − 1/m j 1 − 1/2d − 1 − yh− j+1 − (2d − 1)ydh− j

(2)

j = 1, . . . , h
4.3. Instance 2h + 1
(1+)yh
for some large enough integer K such that u ∈ I1,h , v ∈ I 2 , t ∈ Iλ and
Let u = 1+
2 , v = (1 + )yh and t =
2K
K
∈
N.
For
these
item
sizes,
the
algorithm
is
not allowed to combine u-items with v-items in the same bin. We
yh
1+
define anchor points as follows: (0, 0) for type u; all points with coordinates equal to 1+
2 or 2 − (1 + )yh for type
(1+)yh
v; all points with coordinates equal to i 2K for type t. As before, the anchor points for u and v-items are a subset
of the t-items’ anchor points, and so we can pack one u-item together with 2d − 1 v-items and M t-items if we choose

d  d
h
M = 2K−y
− yKh − (2d − 1) (2K)d .
yh
d

For this input, any Harmonic-type algorithm uses at least N bins for u-items, N 2 2−1
= N(1 −
d
NM
and  2K−y
d bins for t-items. This gives in total

1
)
2d

bins for v-items

h

yh


!d
!d 


K
1
2Ky
h
d

N 2 − d + 1 −
− (2 − 1)
2K − yh
2K − yh 
2
!
1
K→∞
d
d
−−−−→ N 3 − d−1 − (2 − 1)yh
2
bins. We therefore can derive the following lower bound on the performance ratio:
RA ≥ 3 − 1/2d−1 − (2d − 1)ydh

(3)

4.4. Combined Lower Bound
Given a certain set of parameters (y j and m j ), the maximum of the three right sides of inequalities (1), (2) and (3)
give us a bound on the competitive ratio of any Harmonic-type algorithm with this set of parameters. In order to get
a general (worst-case) lower bound on RA , we need to find the minimum of this maximum over all possible sets of
parameters.
This lower bound for RA is obtained when equality holds in all of the inequalities (1), (2) and (3). To see this,
consider the following: We have 2h+1 variables and 2h+1 constraints. For j ∈ {1, . . . , h}, we see that (1) is increasing
in m j and (2) is decreasing in m j . Next, let c ∈ {1, . . . , h − 1}. We see that (1) for j = h − c ∈ {1, . . . , h − 1} is decreasing
in yc , and (2) for j = h − c + 1 ∈ {2, . . . , h} is increasing in yc . Finally, we have that (2) for j = 1 is increasing in yh and
(3) is decreasing in yh . This means, given certain parameters y j and m j , if e.g. (3) gives a smaller lower bound on RA
than (2) with j = 1 does, we can decrease the value of yh such that the maximum of the three lower bounds becomes
smaller.
Setting the right hand side of (1) equal to the right hand side of (2), gives us m1j = (1 − yh− j+1 )d − 21d or alternatively
1
mh− j+1

= (1 − y j )d −

1
.
2d

Plugging this into (1) (replacing j by h − j + 1), we find that
 d
1/d
 −2 RA + 2d ydj−1 − 4d ydj−1 − 1 + 3 · 2d − 1/2d 

y j = 1 − 
2d − 1
14

(4)

Recall that we require 1/3 = y0 < y1 . From this, combined with (4) for j = 1, we obtain that
RA ≥ 3 − 2

2d − 1 2d + 1
−
3d
4d

We list some values of the lower bound for several values of d in Table 10.
d=

1

2

3

4

5

6

∞

RA >

1.58333

2.02083

2.34085

2.56322

2.71262

2.81129

3

Table 10: Lower bounds for Harmonic-type algorithms in dimensions 1 to 6 and limit for d → ∞.

Note that for d = 1, our formula yields the bound of Ramanan et al. [6]. Surprisingly, it does not seem to help to
analyze the values of y2 , . . . , yh . Especially, equations involving y j for j > 1 become quite messy due to the recursive
nature of (4). If h is a very small constant like 1 or 2, we can derive better lower bounds for RA . For larger h, we can
use the inequalities y1 < yh , y2 < yh , y3 < yh (i.e. assuming that h > 3) to derive upper bounds on the best value RA
that could possibly be proven using this technique. These upper bounds are very close to 2.02 and suggest that for
larger h, an algorithm in the class C (h) could come very close to achieving a ratio of 2.02 for these inputs. However,
since the inequalities become very unwieldy, we do not prove this formally.
Theorem 2. No Harmonic-type algorithm for two-dimensional online hypercube packing can achieve an asymptotic
performance ratio better than 2.0208.
5. Further Lower Bounds
Inspired by [1], one could try to improve online algorithms for packing 2-dimensional squares by incorporating
two ideas from the one-dimensional case: combining large items (i.e. items larger than 1/2) and medium items (i.e.
items with size in (1/3, 1/2]) whenever they fit together (ignoring their type), and postponing the coloring decision.
The former is intuitive, while the idea of the latter would be the following: When items of a certain type arrive, we first
give them provisional colors and pack them into separate bins (i.e. one item per bin). After several items of this type
arrived, we choose the smallest of them to be red and all others are colored blue. With following items of this type,
we fill up the bins with additional items. However, simply adding two more red items to the bin with a single red item
might be problematic: When filling up the red bins with two more red items, it could happen that these later red items
are larger than the first one - negating the advantage of having the first red item be relatively small. Alternatively,
we could leave the red item alone in its bin. This way, we make sure that at most 3/4 of the blue items of a certain
medium type are smaller than the smallest red item of this type, but we have more wasted space in this bin.
For both approaches discussed above we will show lower bounds on the competitive ratio that are only slightly
lower or even higher than the lower bound established in Section 4 for Harmonic-type algorithms.
5.1. Always combining large and medium items
First, we consider algorithms that combine small and large items whenever they fit together. We define a class of
algorithms B1 that distinguish, possibly among others, the following disjoint subintervals (types):
• Im = (1/3, y] for some y ∈ (1/3, 1/2]
• Iλ = (0, λ]
These algorithms satisfy the following rules:
1. There is a parameter α s.t. an α-fraction of the items of side length in Im are packed 3 per bin (“red items”), the
rest are packed 4 per bin (“blue items”).
2. No bin that contains an item of side length in Iλ contains an item of side length larger than 1/2 or an item of
side length in Im .
15

3. Items of type Im are packed without regard to their size.
Let a, b ∈ Im , a < b. We consider two different inputs, both starting with the same set of items: α3 N items of size
b and (1 − α/3)N items of size a (i.e. in total N items of size a and b). By rule 3, the adversary knows beforehand
which item will be packed in which bin, as they belong to the same type. Hence, the adversary can order these items
in such a way that the items colored blue by the algorithm are all a-items, and in each bin with red items, there are
3+α
two a- and one b-item. By rule 1, the online algorithm uses ( α3 + 1−α
4 )N = 12 N bins for items of this type.
The sizes a and b will tend towards 1/3, as this way the adversary can maximize the total volume of sand (infinitesimally small items) that can be added to any bin in the optimal solution while not changing the way the algorithm
packs these items and increasing the number of bins the algorithm needs for packing the sand items. Therefore, we
will assume that a and b are arbitrarily close to 1/3.
items of size 1 − a arrive, followed by sand of total volume
In the first input, after these medium items, (1−α/3)N
3
(1−α/3)N
24+7α
α
324 N. In the optimal solution, we can pack 12 N bins with four b-items and sand of volume 5/9 each, and
3
α
2
α
bins with three a-items, one (1 − a)-item and sand of volume 12 N · 9 each. Hence, the optimal solution uses 12
N+
(1−α/3)N
12−α
= 36 N bins.
3
The algorithm, however, cannot pack a large item into any of the bins with red medium items, as these always
(1−α/3)N
bins for large
contain a b-item. Hence, in addition to the 3+α
12 N bins for medium items, the algorithm needs
3
24+7α
213−2α
items and at least 324 N bins for sand. This gives in total at least 324 N bins, and a competitive ratio of at least
213−2α
324 N
12−α
36 N

=

213 − 2α
9(12 − α)

(5)

In the second input, after the medium items, N/3 items of size 1/2 +  will arrive, followed by sand of total volume
The optimal solution packs all medium items three per bin, using N/3 bins, and adds one large item and sand of
volume 15/36 in each such bin. In the algorithm’s solution, large items can only be added to the αN/3 bins containing
three red items, i.e. it needs additional N/3 − αN/3 bins for the remaining N/3 − αN/3 large items. Finally, the
algorithm uses at least 5/36N bins for sand. The algorithm therefore uses in total at least 3+α
12 N +(1−α)N/3+5/36N =
26−9α
36 N bins. This gives a competitive ratio of at least
5
36 N.

3(26 − 9α) 26 − 9α
=
36
12

(6)

Observe that (5) is increasing in α, while (6) is decreasing in α. Hence, the minimum
over the maximum of the
√
197− 36541
≈ 0.2164. For this α,
two bounds is obtained for the α-value that makes both bounds equal, which is α =
27
both bounds become larger than 2.0043.
Theorem 3. No algorithm in class B1 for two-dimensional online hypercube packing can achieve a competitive ratio
of less than 2.0043.
5.2. Packing red medium items one per bin, postponing the coloring
Now, consider the algorithm that packs red items alone into bins and makes sure that at most 3/4 of the blue items
of a certain type are smaller than the smallest red item of this type. We define a new class of algorithms B2 that
distinguish, possibly among others, the following disjoint subintervals (types):
• Im = (1/3, y]
• Iλ = (0, λ]
Furthermore, algorithms in B2 satisfy the following rules:
1. There is a parameter α s.t. an α-fraction of the items of side length in Im are packed 1 per bin (“red items”), the
rest are packed 4 per bin (“blue items”).
2. No bin that contains an item of side length in Iλ contains an item of side length larger than 1/2 or an item of
side length in Im .
16

3. Items of side length in Im are initially packed one per bin. At some regular intervals, the algorithm fixes some
of these items to be red, and does not pack additional items of the same type witht them.
From rule 3 we can conclude that the algorithm gives the following guarantee: 3/4 of the blue items with size in
Im are not smaller than the smallest red item with size in Im .
Let a, b ∈ Im , a < b as before. We again consider two different inputs, both starting with the same set of items:
3(1−α)
αN + 1−α
4 N items of size b, and
4 N items of size a. They arrive in such an order that all red items are b-items,
and all bins with blue items contain one b- and three a-items. We require the b-item in the blue bins because of the
postponement of the coloring: If the first blue item in a bin was an a-item, the algorithm would choose this item to
1+3α
become red and not one of the b-items. By rule 1, the algorithm needs 1−α
4 N + αN = 4 N bins for these N items.
1−α
In the first input, after the medium items arrived, we get 4 N large items of size 1 − a, followed by sand of total
1−α
volume 13+7α
144 N. The optimal solution can pack the a-items three per bin together with one (1 − a)-item, using 4 N
α 1−α
bins for these items. The b-items are packed four per bin, using ( 4 + 16 )N bins. Note that the empty volume in all bins
2
α
1−α
5
13+7α
of these two types is 1−α
4 N · 9 + ( 4 + 16 )N · 9 = 144 N, i.e. it equals exactly the volume of the sand, so the sand can
α
1−α
5−α
be filled in these holes without using further bins. Hence, the optimal number of bins is 1−α
4 N + ( 4 + 16 )N = 16 N.
1+3α
The algorithm uses, as discussed before, 4 N bins for the medium items of size a and b. The large items cannot
be added to red medium items, as they do not fit together, thus the algorithm uses 1−α
4 N additional bins for the large
items. Finally, according to rule 2, at least 13+7α
N
additional
bins
are
needed
to
pack
the sand. This gives in total at
144
1−α
13+7α
85+79α
least 1+3α
N
+
N
+
N
=
N
bins.
We
find
that
the
competitive
ratio
is
at
least
4
4
144
144
85+79α
144 N
5−α
16 N

=

85 + 79α
9(5 − α)

(7)

In the second input, N/3 items of size 1/2 +  arrive after the medium items, followed by sand of total volume
5/36N. The algorithm packs this input the same way as a B1 algorithm, so the analysis carries over. We get a
competitive ratio of at least
26−9α
26 − 9α
36 N
=
(8)
N/3
12
It can be seen that (7) is a function increasing in α, while (8) is decreasing
in α, hence the minimum over the
√
maximum of two bounds is reached when they are equal. In that case, α = 529− 54274441 ≈ 0.0950, and the lower bound
for the competitive ratio becomes larger than 2.0954.
Theorem 4. No algorithm in class B2 for two-dimensional online hypercube packing can achieve a competitive ratio
of less than 2.0954.
Note here that this is an even higher lower bound than the one shown in the previous Subsection 5.1, although we
use postponement of the coloring here. This indicates that the space we waste by packing red medium items separately
outweighs the advantage we get by having a guarantee about the size of the red item.
6. Conclusion
We have given improved general lower bounds as well as lower bounds for an important subclass of algorithms.
We believe that our lower bound of 1.859 for rectangle packing could be further improved to 1.907 by extending the
input sequence as given in Table 11. However, we do not have a formal proof of what the heaviest patterns are for the
sets T i (our conjectures are listed in Table 12).
The main open question is how to reduce the gap between the upper and lower bounds for these problems, which
remain fairly large.

17

type j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

width w j
1/4 − 30000δ
1/4 + 10000δ
1/2 + 20000δ
1/4 − 3000δ
1/4 + 1000δ
1/2 + 2000δ
1/4 − 300δ
1/4 + 100δ
1/2 + 200δ
1/4 − 30δ
1/4 + 10δ
1/2 + 20δ
1/4 − 3δ
1/4 + δ
1/2 + 2δ

height h j
1/1807 + 
1/43 + 
1/7 + 
1/3 + 
1/2 + 

OPT (L1 . . . L j )/n · 7224
1
2
4
46
88
172
430
688
1204
1806
2408
3612
4515
5418
7224

Table 11: The input items for a lower bound of 1.907.

j
1
2

types to consider
1
2, 4

3

3,4

4
5

4
5, 7

6

6, 7

7

7

8

8, 10

9
10
11

9, 10
10
11, 13

12

12,13

13
14
15

13
14
15

heaviest patterns p from T j
7224 × s1
5418 × s2
1806 × s3 , 43 × s4
84 × s3 , 166 × s4
168 × s4
126 × s5
42 × s6 , 7 × s7
12 × s6 , 22 × s7
24 × s7
18 × s8
6 × s8 , 8 × s10
4 × s9 , 6 × s10
8 × s10
3 × s11 , 4 × s13
2 × s12 , 2 × s13
1 × s12 , 4 × s13
4 × s13
3 × s14
1 × s15

w(p) · 516211/516
7224
5418
4816
4704
3528
3136
2688
2016
1904
1344
1176
1008
672
504
336

Table 12: We believe that these are the patterns that need to be considered for verifying the feasibility of the dual solution of the 1.907 lower bound.

18

References
[1] S. Heydrich, R. van Stee, Beating the harmonic lower bound for online bin packing, CoRR abs/1511.00876, http://arxiv.org/abs/1511.00876.
[2] J. D. Ullman, The performance of a memory allocation algorithm, Tech. Rep. 100, Princeton University, Princeton, NJ (1971).
[3] D. S. Johnson, A. J. Demers, J. D. Ullman, M. R. Garey, R. L. Graham, Worst-case performance bounds for simple one-dimensional packing
algorithms, SIAM J. Comput. 3 (4) (1974) 299–325. doi:10.1137/0203025.
[4] D. S. Johnson, Fast algorithms for bin packing, J. Comput. Syst. Sci. 8 (3) (1974) 272–314. doi:10.1016/S0022-0000(74)80026-7.
[5] C.-C. Lee, D.-T. Lee, A simple on-line bin-packing algorithm, J. ACM 32 (3) (1985) 562–572. doi:10.1145/3828.3833.
[6] P. V. Ramanan, D. J. Brown, C.-C. Lee, D.-T. Lee, On-line bin packing in linear time, J. Algorithms 10 (3) (1989) 305–326. doi:10.1016/
0196-6774(89)90031-X.
[7] S. S. Seiden, On the online bin packing problem, J. ACM 49 (5) (2002) 640–671. doi:10.1145/585265.585269.
[8] J. Balogh, J. Békési, G. Dósa, L. Epstein, A. Levin, A new and improved algorithm for online bin packingarXiv:1707.01728v1.
[9] J. Balogh, J. Békési, G. Galambos, Approximation and Online Algorithms: 8th International Workshop, WAOA 2010, Liverpool, UK,
September 9-10, 2010. Revised Papers, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, Ch. New Lower Bounds for Certain Classes of
Bin Packing Algorithms, pp. 25–36. doi:10.1007/978-3-642-18318-8_3.
URL http://dx.doi.org/10.1007/978-3-642-18318-8_3
[10] D. Coppersmith, P. Raghavan, Multidimensional on-line bin packing: Algorithms and worst-case analysis, Oper. Res. Lett. 8 (1) (1989) 17 –
20. doi:10.1016/0167-6377(89)90027-8.
[11] J. Csirik, A. van Vliet, An on-line algorithm for multidimensional bin packing, Oper. Res. Lett. 13 (3) (1993) 149 – 158. doi:10.1016/
0167-6377(93)90004-Z.
[12] L. Epstein, R. van Stee, Optimal online algorithms for multidimensional packing problems, SIAM J. Comput. 35 (2) (2005) 431–448.
doi:10.1137/S0097539705446895.
[13] X. Han, F. Y. L. Chin, H. Ting, G. Zhang, Y. Zhang, A new upper bound 2.5545 on 2d online bin packing, ACM Transactions on Algorithms
7 (4) (2011) 50. doi:10.1145/2000807.2000818.
[14] L. Epstein, R. van Stee, Online square and cube packing, Acta Inf. 41 (9) (2005) 595–606. doi:10.1007/s00236-005-0169-z.
[15] A. van Vliet, Lower and upper bounds for online bin packing and scheduling heuristics, Ph.D. thesis, Erasmus University, Rotterdam, The
Netherlands (1995).
[16] X. Han, D. Ye, Y. Zhou, A note on online hypercube packing, Cent. Europ. J. Oper. Re. 18 (2) (2010) 221–239. doi:10.1007/
s10100-009-0109-z.
[17] J. Balogh, J. Békési, G. Dósa, L. Epstein, A. Levin, Lower bounds for several online variants of bin packing.arXiv:1708.03228v1.
[18] L. Epstein, R. van Stee, Bounds for online bounded space hypercube packing, Discrete Optim. 4 (2) (2007) 185–197. doi:10.1016/j.
disopt.2006.11.005.

19

