A Two-Phase Algorithm for Bin Stretching with
Stretching Factor 1.5
Martin Böhm1,? , Jiřı́ Sgall1,? , Rob van Stee2 and Pavel Veselý1,?

arXiv:1601.08111v2 [] 20 Aug 2016

1

Computer Science Institute of Charles University, Prague, Czech Republic.
{bohm,sgall,vesely}@iuuk.mff.cuni.cz.
2
Department of Computer Science, University of Leicester, Leicester, UK.
rob.vanstee@leicester.ac.uk.

Abstract. Online Bin Stretching is a semi-online variant of bin packing in which the
algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly
overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum
size packed into any bin.
We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any
number of bins. We build on previous algorithms and use a two-phase approach. However,
our analysis is technically more complicated and uses amortization over the bins with the
help of two weight functions.

1

Introduction

The most famous algorithmic problem dealing with online assignment is arguably
Online Bin Packing. In this problem, known since the 1970s, items of size between
0 and 1 arrive in a sequence and the goal is to pack these items into the least number
of unit-sized bins, packing each item as soon as it arrives.
Online Bin Stretching, which has been introduced by Azar and Regev in
1998 [3,4], deals with a similar online scenario. Again, items of size between 0 and
1 arrive in a sequence, and the algorithm needs to pack each item as soon as it
arrives, but there are the following differences: (i) The packing algorithm knows m,
the number of bins that an optimal offline algorithm would use, and must also use
only at most m bins, and (ii) the packing algorithm can use bins of capacity R for
some R ≥ 1. The goal is to minimize the stretching factor R.
In general, the term “semi-online” refers to algorithms that, compared to online
algorithms, have some additional global information about the instance of the problem
or have another advantage. We have formulated Online Bin Stretching as a
semi-online bin packing variant, where the algorithm has the additional information
that the optimal number of bins is m and at the same time the algorithm has the
advantage of using bins of larger capacity.
Taking another view, Online Bin Stretching can also be thought of as a
semi-online scheduling problem, in which we schedule jobs arriving one by one in an
online manner on exactly m machines, with the objective to minimize the makespan,
i.e., the length of the resulting schedule. Here the additional information is that the
optimal offline algorithm could schedule all jobs with makespan 1. Our task is to
present an algorithm with makespan being at most R.
History. Online Bin Stretching has been proposed by Azar and Regev [3,4].
The original lower bound of 4/3 for three bins has appeared even before that, in [16],
?

Supported by the project 14-10003S of GA ČR and by the GAUK project 548214.

for two bins together with a matching algorithm. Azar and Regev extended the same
lower bound to any number of bins and gave an online algorithm with a stretching
factor 1.625.
The problem has been revisited recently, with both lower bound improvements
and new efficient algorithms. On the algorithmic side, Kellerer and Kotov [15]
have achieved a stretching factor 11/7 ≈ 1.57 and Gabay et al. [12] have achieved
26/17 ≈ 1.53. There is still a considerable gap to the best known general lower bound
of 4/3, shown by a simple argument in the original paper of Azar and Regev [3,4].
While the algorithms and the lower bound from the last paragraph work for
any m ≥ 2, Online Bin Stretching has also been studied in the special case of
a specific constant number of bins m. In some cases better algorithms and lower
bounds are possible. Obviously, for m = 1, the problem is trivial, as the only possible
algorithm has a stretching factor 1. For m = 2, it is easy to achieve a stretching
factor 4/3, which is optimal. Thus the first interesting case is m = 3; the currently
best algorithm given by the authors of this paper [7] has a stretching factor of
11/8 = 1.375.
Interestingly, the setting with a small fixed number of bins allows better lower
bounds on the stretching factor. The lower bounds cannot be easily translated into a
lower bound for a larger m; for example, if we modify the instance by adding new bins
and a corresponding number of items of size 1 (that must use exactly the new bins
in the optimum), the semi-online algorithm still could use the additional capacity
of R − 1 in the new bins to its advantage. The paper of Gabay et al. [10] showed a
lower bound of 19/14 ≈ 1.357 for m = 3 using a computer search. Extending their
methods, the authors of this paper were able to reach a lower bound of 15/11 = 1.36
for m = 3 in [7] as well as a bound of 19/14 for m = 4 and m = 5. The preprint
[10] was updated in 2015 [11] to include a lower bound of 19/14 for m = 4 bins. For
m > 5, the general lower bound of 4/3 is still the best currently known.
Our contributions. We present a new algorithm for Online Bin Stretching
with a stretching factor of 1.5. We build on the two-phase approach which appeared
previously in [15,12]. In this approach, the first phase tries to fill some bins close
to R − 1 and achieve a fixed ratio between these bins and empty bins, while the
second phase uses the bins in blocks of fixed size and analyzes each block separately.
To reach 1.5, we needed to significantly improve the analysis using amortization
techniques (represented by a weight function in our presentation) to amortize among
blocks and bins of different types.
A preliminary version of this work appeared in [6].
Related work. The NP-hard problem Bin Packing was originally proposed by
Ullman [18] and Johnson [14] in the 1970s. Since then it has seen major interest
and progress, see the survey of Coffman et al. [8] for many results on classical Bin
Packing and its variants. While our problem can be seen as a variant of Bin
Packing, note that the algorithms cannot open more bins than the optimum and
thus general results for Bin Packing do not translate to our setting.
As noted, Online Bin Stretching can be formulated as online scheduling
on m identical machines with known optimal makespan. Such algorithms were
studied and are important in designing constant-competitive algorithms without the
2

additional knowledge, e.g., for scheduling in the more general model of uniformly
related machines [2,5,9].
For scheduling, also other types of semi-online algorithms are studied. Historically
first is the study of ordered sequences with non-decreasing processing times [13]. Most
closely related is the variant with known sum of all processing times studied in [16].
If we know the optimal makespan, we can always pad the instance by small items at
the end so that the optimal makespan remains the same and the sum of processing
time equals m times the optimal makespan. Thus one could expect that these two
quantities are interchangeable. However, when the sum of all processing times is
known, the currently best results are a lower bound of 1.585 and an algorithm with
ratio 1.6, both from [1]. This shows, somewhat surprisingly, that knowing the actual
optimum gives a significantly bigger advantage to the semi-online algorithm over
knowing just the sum of the processing times. See Pruhs et al. [17] for a survey of
other results on (semi-)online scheduling.
1.1

Definitions and notation

Our main problem, Online Bin Stretching, can be described as follows:
Input: an integer m and a sequence of items I = i1 , i2 , . . . given online one by one.
Each item has a size s(i) ∈ [0, 1] and must be packed immediately and irrevocably.
Parameter: The stretching factor R ≥ 1.
P
Output: Partitioning (packing) of I into bins B1 , . . . , Bm so that i∈Bj s(i) ≤ R
for all j = 1, . . . , m.
Guarantee: there exists a packing of all items in I into m bins of capacity 1.
Goal: Design an online algorithm with the stretching factor R as small as possible
which packs all input sequences satisfying the guarantee.
P
For a bin B, we define the size of the bin s(B) = i∈B s(i). Unlike s(i), s(B)
can change during the course of the algorithm, as we pack more and more items into
the bin. To easily differentiate between items, bins and lists of bins, we use lowercase
letters for items (i, b, x), uppercase letters for bins and other sets of items (A, B,
X), and calligraphic letters for lists of bins (A, C, L).

2

Algorithm

We rescale the sizes of items and the capacities of bins so that the optimal bins have
capacity 12 and the bins of the algorithm have capacity 18.
We follow the general two-phase scheme of recent results [15,12] which we sketch
now. In the first phase of the algorithm we try to fill the bins so that their size is
at most 6, as this leaves space for an arbitrary item in each bin. Of course, if items
larger than 6 arrive, we need to pack them differently, preferably in bins of size at
least 12 (since that is the size of the optimal bins). We stop the first phase when the
number of non-empty bins of size at most 6 is three times the number of empty bins.
In the second phase, we work in blocks consisting of three non-empty bins and one
empty bin. The goal is to show that we are able to fill the bins so that the average
size is at least 12, which guarantees we are able to pack the total size of 12m which
is the upper bound on the size of all items.
3

The limitation of the previous results using this scheme was that the volume
achieved in a typical block of four bins is slightly less than four times the size of the
optimal bin, which then leads to bounds strictly above 3/2. This is also the case in
our algorithm: A typical block may have three bins with items of size just above 4
from the first phase plus one item of size 7 from the second phase, while the last
bin contains two items, each of size 7, from the second phase—a total of 47 instead
of desired 4 · 12. However, we notice that such a block contains five items of size 7
which the optimum cannot fit into four bins. To take an advantage of this, we cannot
analyze each block separately as in [15,12]. Instead, the rough idea of our improved
method is to show that a bin with no item of size more than 6 typically has size at
least 13 and amortize among the blocks of different types. Technically this is done
using a weight function w that takes into account both the total size of items and
the number of items larger than 6. This is the main new technical idea of our proof.
There are other complications. We would like to ensure that a typical bin of size
at most 6 has size at least 4 after the first phase. However, this is impossible to
guarantee if the items packed there have size between 3 and 4. Larger items are fine,
as one per bin is sufficient, and the smaller ones are fine as well as we can always fit
at least two of them. It is crucial to consider the items with sizes between 3 and 4
very carefully. This motivates our classification of items: Only the regular items of
size in (0, 3] ∪ (4, 6] are packed in the bins filled up to size 6. The medium items of
size in (3, 4] are packed in their own bins (four or five per bin). Similarly, large items
of size in (6, 9] are packed in pairs in their own bins. Finally, the huge items of size
larger than 9 are handled similarly as in the previous papers: If possible, they are
packed with the regular items, otherwise each in their own bin.
The introduction of medium size items implies that we need to revisit the analysis
of the first phase and also of the case when the first phase ends with no empty bin.
These parts of the proof are similar to the previous works, but due to the new item
type we need to carefully revisit it; it is now convenient to introduce another function
v that counts the items according to their type; we call it a value, to avoid confusion
with the main weight function w. The analysis of the second phase when empty bins
are present is more complicated, as we need to take care of various degenerate cases,
and it is also here where the novel amortization is used.
Now we are ready to proceed with the formal definitions, statement of the
algorithm, and the proof our main result.
Theorem 2.1. There exists an algorithm for Online Bin Stretching with a
stretching factor of 1.5 for an arbitrary number of bins.
We take an instance with an optimal packing into m bins of size at most 12
and, assuming that our algorithm fails, we derive a contradiction. One way to get
a contradiction is to show that the size of all items is larger than 12m. As stated
above, we also use two bounds in the spirit of weight functions: weight w(i) and
value v(i). The weight w(i) is a slightly modified size to account for items of size
larger than 6. The value v(i) only counts the number of items with relatively large
sizes. For our calculations, it is convenient to normalize the weight w(i) and value
v(i) so that they are at most 0 for bins in the optimal packing (see Lemma 2.3). To
4

get a contradiction, it is then sufficient to prove that the total weight or value of all
bins is positive.
We classify the items based on their size s(i) and define their value v(i) as follows.
s(i)

(9, 12]

(6, 9]

(3, 4]

type
v(i)

huge
3

large
2

medium
1

(0, 3] ∪ (4, 6]
regular
0

P
Definition 2.2. For a set of items A, we define the value v(A) = ( i∈A v(i)) − 3.
Furthermore we define weight w(A) as follows. Let k(A) be the number of large
and huge items in A. Then w(A) = s(A) + k(A)
P − 13.
P
For a
set
of
bins
A
we
define
v(A)
=
v(A),
w(A)
=
A∈A
A∈A w(A) and
P
k(A) = A∈A k(A).

Lemma 2.3. For any packing A of a valid input instance into m bins of an arbitrary
capacity, we have w(A) ≤ 0 and v(A) ≤ 0.
Proof. For the value v(A), no optimal bin can contain items with the sum of their
values larger than 3. The bound follows by summing over all bins and the fact that
the number of bins is the same for the optimum and the considered packing.
For w(A), we have s(A) ≤ 12m and k(A) ≤ m, as the optimum packs all items
in m bins of volume 12 and no bin can contain two items larger than 6. Thus
w(A) = s(A) + k(A) − 13m ≤ 12m + m − 13m = 0.
t
u

12
6
3
E

G

H L

M T

R

Fig. 1. An illustration of bin types during the first phase.

First phase. During the first phase, our algorithm maintains the invariant that only
bins of the following types exist. See Figure 1 for an illustration of the bin types.
Definition 2.4. Given a bin A, we define the following bin types and introduce
letters that typically denote those bins:
– Empty bins (E): bins that have no item.
– Complete bins (G): all bins that have w(A) ≥ 0 and s(A) ≥ 12;
– Huge-item bins (H): all bins that contain a huge item (plus possibly some other
items) and have s(A) < 12;
– One large-item bin (L): a bin containing only a single large item;
– One medium-item bin (M): a non-empty bin with s(A) < 13 and only medium
items;
5

– One tiny bin (T): a non-empty bin with s(A) ≤ 3;
– Regular bins (R): all other bins with s(A) ∈ (3, 6];
First-phase algorithm:
During the algorithm, let e be the current number of empty bins and r the
current number of regular bins.
(1) While r < 3e, consider the next item i and pack it as follows, using bins of
capacity 18; if more bins satisfy a condition, choose among them arbitrarily:
(2)
If i is regular:
(3)
If there is a huge-item bin, pack i there.
(4)
Else, if there is a regular bin A with s(A) + s(i) ≤ 6, pack it there.
(5)
Else, if there is a tiny bin A with s(A) + s(i) ≤ 6, pack it there.
(6)
If i is medium and there is a medium-item bin where i fits, pack it there.
(7)
If i is large and there is a large-item bin where i fits, pack it there.
(8)
If i is huge:
(9)
If there is a regular bin, pack i there.
(10)
Else, if there is a tiny bin, pack i there.
(11) If i is still not packed, pack it in an empty bin.
First we observe that the algorithm described in the box above is properly defined.
The stopping condition guarantees that the algorithm stops when no empty bin is
available. Thus an empty bin is always available and each item i is packed. We now
state the basic properties of the algorithm.
Lemma 2.5. At any time during the first phase the following holds:
(i) All bins used by the algorithm are of the types from Definition 2.4.
(ii) All complete bins B have v(B) ≥ 0.
(iii) If there is a huge-item bin, then there is no regular and no tiny bin.
(iv) There is at most one large-item bin and at most one medium-item bin.
(v) There is at most one tiny bin T . If T exists, then for any regular bin, s(T ) +
s(R) > 6. There is at most one regular bin R with s(R) ≤ 4.
(vi) At the end of the first phase 3e ≤ r ≤ 3e + 3.
Proof. (i)-(v): We verify that these invariants are preserved when an item of each
type arrives and also that the resulting bin is of the required type; the second part is
always trivial when packing in an empty bin.
If a huge item arrives and a regular bin exists, it always fits there, thus no
huge-item bin is created and (iii) cannot become violated. Furthermore, the resulting
size is more than 12, thus the resulting bin is complete. Otherwise, if a tiny bin
exists, the huge item fits there and the resulting bin is either complete or huge. In
either case, if the bin is complete, its value is 0 as it contains a huge item.
If a large item arrives, it always fits in a large-item bin if it exists and makes
it complete; its value is at least 1, as it contains two large items. Thus a second
large-item bin is never created and (iv) is not violated.
If a medium item arrives, it always fits in a medium-item bin if it exists; the
bin is then complete if it has size at least 13 and then its value is at least 1, as it
contains 4 or 5 medium items; otherwise the bin type is unchanged. Again, a second
medium-item bin is never created and (iv) is not violated.
6

If a regular item arrives and a huge-item bin exists, it always fits there, thus no
regular bin is created and (iii) cannot become violated. Furthermore, if the resulting
size is at least 12, the bin becomes complete and its value is 0 as it contains a huge
item; otherwise the bin type is unchanged.
In the last case, a regular item arrives and no huge-item bin exists. The algorithm
guarantees that the resulting bin has size at most 6, thus it is regular or tiny. We
now proceed to verify (v). A new tiny bin T can be created only by packing an item
of size at most 3 in an empty bin. First, this implies that no other tiny bin exists, as
the item would be put there, thus there is always at most one tiny bin. Second, as
the item is not put in any existing regular bin R, we have s(R) + s(T ) > 6 and this
also holds later when more items are packed into any of these bins. A new regular
bin R with s(R) ≤ 4 can be created only from a tiny bin; note that a bin created
from an empty bin by a regular item is either tiny or has size in (4, 6]. If another
regular bin with size at most 4 already exists, then both the size of the tiny bin and
the size of the new item are larger than 2 and thus the new regular bin has size more
than 4. This completes the proof of (v).
(vi): Before an item is packed, the value 3e − r is at least 1 by the stopping
condition. Packing an item may change e or r (or both) by at most 1. Thus after
packing an item we have 3e − r ≥ 1 − 3 − 1 = −3, i.e., r ≤ 3e + 3. If in addition
3e ≤ r, the algorithm stops in the next step and (vi) holds.
t
u
If the algorithm packs all items in the first phase, it stops. Otherwise according
to Lemma 2.5(iii) we split the algorithm in two very different branches. If there is at
least one huge-item bin, follow the second phase with huge-item bins below. If there
is no huge-item bin, follow the second phase with regular bins.
Any bin that is complete is not used in the second phase. In addition to complete
bins and either huge-item bins, or regular and empty bins, there may exist at
most three special bins denoted and ordered as follows: the large-item bin L, the
medium-item bin M , and the tiny bin T .
Second phase with huge-item bins. In this case, we assume that a huge-item
bin exists when the first phase ends. By Lemma 2.5(iii), we know that no regular
and tiny bins exist. There are no empty bins either, as we end the first phase with
3e ≤ r = 0. With only a few types of bins remaining, the algorithm for this phase is
very simple:
Algorithm for the second phase with huge-item bins:
Let the list of bins L contain first all the huge-item bins, followed by the special
bins L, M , in this order, if they exist.
(1) For any incoming item i:
(2)
Pack i using First Fit on the list L, with all bins of capacity 18.
Suppose that we have an instance that has a packing into bins of capacity 12 and
on which our algorithm fails. We may assume that the algorithm fails on the last
item f . By considering the total volume, there always exists a bin with size at most
12. Thus s(f ) > 6 and v(f ) ≥ 2.
If during the second phase an item n with s(n) ≤ 6 is packed into the last bin in
L, we know that all other bins have size more than 12, thus all the remaining items fit
7

into the last bin. Otherwise we consider v(L). Any complete bin B has v(B) ≥ 0 by
Lemma 2.5(ii) and each huge-item bin gets nonnegative value, too. Also v(L) ≥ −1
if L exists. This shows that M must exist, since otherwise v(L) + v(f ) ≥ −1 + 2 ≥ 1,
a contradiction.
Now we know that M exists, furthermore it is the last bin and thus we also know
that no regular item is packed in M . Therefore M contains only medium items from
the first phase and possibly large and/or huge items from the second phase. We claim
that v(M ) + v(f ) ≥ 2 using the fact that f does not fit into M and M contains no
item a with v(a) = 0: If f is huge we have s(M ) > 6, thus M must contain either
two medium items or at least one medium item together with one large or huge
item and v(M ) ≥ −1. If f is large, we have s(M ) > 9; thus M contains either three
medium items or one medium and one large or huge item and v(M ) ≥ 0. Thus we
always have v(L) ≥ −1 + v(M ) + v(f ) ≥ 1, a contradiction.
Second phase with regular bins. Let E resp. R be the set of empty resp. regular
bins at the beginning of the second phase, and let e = |E|. Let λ ∈ {0, 1, 2, 3} be
such that |R| = 3e + λ; Lemma 2.5(vi) implies that λ exists. Note that it is possible
that R = ∅, in that case e = λ = 0.
We organize the remaining non-complete bins into blocks Bi , and then order them
into a list L, as follows:
Definition 2.6. Denote the empty bins E1 , E2 , . . . , Ee . The regular bins are denoted
by Ri,j , i = 1, ..., e + 1, j = 1, 2, 3. The ith block Bi consists of bins Ri,1 , Ri,2 , Ri,3 , Ei
in this order. There are several modifications to this rule:
(1) The first block B1 contains only λ regular bins, i.e., it contains R1,1 , . . . , R1,λ , E1
in this order; in particular, if λ = 0 then B1 contains only E1 .
(2) The last block Be+1 has no empty bin, only exactly 3 regular bins.
(3) If e = 0 and r = λ > 0 we define only a single block B1 which contains r = λ
regular bins R1,1 , . . . , R1,λ .
(4) If e = r = λ = 0, there is no block, as there are no empty and regular bins.
(5) If r > 0, we choose as the first regular bin the one with size at most 4, if there is
such a bin.
Denote the first regular bin by Rfirst . If no regular bin exists (i.e., if r = 0), Rfirst is
undefined.
Note that Rfirst is either the first bin R1,1 in B1 if λ > 0 or the first bin R2,1 in B2 if
λ = 0. By Lemma 2.5(v) there exists at most one regular bin with size at most 4,
thus all the remaining Ri,j 6= Rfirst have s(Ri,j ) > 4.
Definition 2.7. The list of bins L we use in the second phase contains first the
special bins and then all the blocks B1 , . . . , Be+1 . Thus the list L is (some or all of
the first six bins may not exist):
L, M, T, R1,1 , R1,2 , R1,3 , E1 , R2,1 , R2,2 , R2,3 , E2 , . . . , Ee , Re+1,1 , Re+1,2 , Re+1,3 .
Whenever we refer to the ordering of the bins, we mean the ordering in the list L.
See Figure 2 for an illustration.
8

12
6
G

G

G

G

L

M T

R

R

E

R

R

R

E

R

R

R

Fig. 2. A typical state of the algorithm after the first phase. The bin labels correspond to the particular
bin types. G denotes complete bins, other labels are the initial letters of the bin types. The non-complete
bins (other than G) are ordered as in the list L at the beginning of the second phase with regular bins.

Algorithm for the second phase with regular bins:
Let L be the list of bins as in Definition 2.7, with all bins of capacity 18.
(1) For any incoming item i:
(2)
If i is huge, pack it using First Fit on the reverse of the list L.
(3)
In all other cases, pack i using First Fit on the normal list L.
Suppose that we have an instance that has a packing into bins of capacity 12 and
on which our algorithm fails. We may assume that the algorithm fails on the last
item. Let us denote this item by f . We have s(f ) > 6, as otherwise all bins have size
more than 12, contradicting the existence of optimal packing. Call the items that
arrived in the second phase new (including f ), the items from the first phase are old.
See Figure 3 for an illustration of a typical final situation (and also of notions that
we introduce later).
Our overall strategy is to obtain a contradiction by showing that
w(L) + w(f ) > 0 .
In some cases, we instead argue that v(L) + v(f ) > 0 or s(L) + s(f ) > 12|L|. Any
of these is sufficient for a contradiction, as all complete bins have both value and
weight nonnegative and size at least 12.
Let H denote all the bins from L with a huge item, and let h = |H| mod 4. First
we show that the average size of bins in H is large and exclude some degenerate
cases; in particular, we exclude the case when no regular bin exists.
6 ∅ and Rfirst ∈ H,
Lemma 2.8. Let ρ be the total size of old items in Rfirst if R =
otherwise set ρ = 4.
(i) The bins H are a final segment of the list L and H ( E ∪ R. In particular,
R=
6 ∅ and Rfirst is defined.
(ii) We have s(H) ≥ 12|H| + h + ρ − 4.
(iii) If H does not include Rfirst , then s(H) ≥ 12|H| + h ≥ 12|H|.
(iv) If H includes Rfirst , then s(H) ≥ 12|H| + h − 1 ≥ 12|H| − 1.
Proof. First we make an easy observation used later in the proof. If E ∪ R ∪ {T }
contains a bin B with no huge item, then no bin preceding B contains a huge item.
Indeed, if a huge item does not fit into B, then B must contain a new item i of size
at most 9. This item i was packed using First Fit on the normal list L, and therefore
it did not fit into any previous bin. Thus the huge item also does not fit into any
previous bin, and cannot be packed there.
9

Let H0 = H ∩ (E ∪ R). We begin proving our lemma for H0 in place of H. That
is, we ignore the special bins at this stage. The previous observation shows that H0
is a final segment of the list.
We now prove the claims (ii)–(iv) with H0 in place of H. All bins Ri,j with a huge
item have size at least 4 + 9 = 13, with a possible exception of Rfirst which has size at
least ρ + 9 = 13 + ρ − 4, by the definition of ρ. Each Ei with a huge item has size at
least 9. Thus for each i with Ei ∈ H0 , s(Ei ) + s(Ri+1,1 ) + s(Ri+1,2 ) + s(Ri+1,3 ) ≥ 4 · 12,
with a possible exception of i = 1 in the case when λ = 0. Summing over all i with
Ei ∈ H0 and the h bins in R from the first block intersecting H0 , and adjusting
for Rfirst if Rfirst ∈ H0 , (ii) for H0 follows. The claims (iii) and (iv) for H0 are an
immediate consequence as ρ > 3 if Rfirst ∈ H0 and ρ = 4 otherwise.
We claim that the lemma for H follows if H0 ( E ∪ R. Indeed, following the
observation at the beginning of the proof, the existence of a bin in E ∪ R with no
huge item implies that no special bin has a huge item, i.e., H0 = H, and also H0 = H
is a final segment of L. Furthermore, the existence of a bin in E ∪ R together with
3e ≤ r implies that there exist at least one regular bin, thus also Rfirst is defined and
(i) follows. Claims (ii), (iii), and (iv) follow from H0 = H and the fact that we have
proved them for H0 .
Thus it remains to show that H0 ( E ∪ R. Suppose for a contradiction that
0
H = E ∪ R.
If T exists, let o be the total size of old items in T . If also Rfirst exists, Lemma 2.5(v)
implies that o + ρ > 6 > 4, otherwise o + ρ > 4 trivially. In either case, summing
with (ii) we obtain
o + s(H0 ) > 12|H0 | .
(1)
Now we proceed to bound s(H). We have already shown claim (iv) for H0 , i.e.,
s(H0 ) ≥ 12|H0 | − 1. If L or M has a huge item, the size of the bin is at least 12, as
there is an old large or medium item in it. If T has a huge item, then (1) implies
s(T ) + s(H0 ) > 9 + o + s(H0 ) > 9 + 12|H0 |. Summing these bounds we obtain
s(H) > 12|H| − 3 .

(2)

We now derive a contradiction in each of the following four cases.
Case 1: All special bins have a huge item. Then L = H and (2) together with
s(f ) > 6 implies s(L) + s(f ) > 12|L| + 3, a contradiction.
Case 2: There is one special bin with no huge item. Then its size together with f is
more than 18, thus (2) together with s(f ) > 6 implies s(f ) + s(L) > 18 + 12|H| − 3 >
12|L|, a contradiction.
Case 3: There are two special bins with no huge item and these bins are L and M .
Suppose first that M contains a new item n. Then s(L) + s(n) > 18 by the First
Fit packing rule. The bin M contains at least one old medium item. Thus, using
(2), we get s(f ) + s(L) > 6 + s(L) + s(n) + 3 + 12|H| − 3 > 24 + 12|H| = 12|L|, a
contradiction.
If M has no new item, then either f is huge and M has at least two medium
items, or f is large and M has at least three items. In both cases v(M ) + v(f ) ≥ 2.
Also v(L) ≥ −1 since L has a large item, and v(H) ≥ 0 as each bin has a huge item.
Altogether we get that the total value v(L) > 0, a contradiction.
10

Case 4: There are two or three special bins with no huge item, one of them is T .
Observe that the bin T always contains a new item n, as the total size of all old
items in it is at most 3.
If there are two special bins with no huge item, denote the first one by B. As
we observed at the beginning of the proof, if T exists and has no huge item, no
special bin can contain a huge item, thus the third special bin cannot exist. We have
s(B) + s(n) > 18, summing with (1) we obtain s(f ) + s(L) ≥ s(f ) + s(B) + s(n) +
o + s(H0 ) > 6 + 18 + 12|H0 | = 12|L|, a contradiction.
If there are three special bins with no huge item, we have s(f ) + s(L) > 18 and
s(M ) + s(n) > 18. Summing with (1) we obtain s(f ) + s(L) > 18 + 18 + o + s(H0 ) >
36 + 12|H0 | = 12|L|, a contradiction.
t
u
Having proven Lemma 2.8, we can infer existence of the following two important
bins, which (as we will later see) split the instance into three logical blocks:
Definition 2.9.
– Let F , the final bin be the last bin in L before H, or the last bin if H = ∅.
– Let C, the critical bin, be the first bin in L of size at most 12.
First note that both F and C must exist: F exists by Lemma 2.8(i), which also
shows that F ∈ E ∪ R. C exists, as otherwise the total size is more than 12m.
To make our calculations easier, we modify the packing so that f is put into F ,
even though it exceeds the capacity of F . Thus s(F ) > 18 and f (a new item) as well
as all the other new items packed in F or in some bin before F satisfy the property
that they do not fit into any previous bin. See Figure 3 for an illustration of the
definitions.
We start by some easy observations. Each bin, possibly with the exception of
L and M , contains a new item, as it enters the phase with size at most 6, and the
algorithm failed. Only items of size at most 9 are packed in bins before F ; in F itself
only the item f can be huge. The bin F always has at least two new items, one that
did fit into it and f . All the new items in the bins after C are large, except for the
new huge items in H and f which can be large or huge. (Note that at this point of
the proof it is possible that C is after F ; we will exclude this possibility soon.)
More observations are given in the next two lemmata.
Lemma 2.10. (i) Let B be any bin before F . Then s(B) > 9. Furthermore, if
B ∈ E then B contains at least two new items.
(ii) Let B, B 0 , B 00 be any three bins in this order before than or equal to F and let
B 00 contain at least two new items. Then s(B) + s(B 0 ) + s(B 00 ) > 36 + o, where
o is the size of old items in B 00 .
(iii) Let B be arbitrary and let B 0 ∈ R be an arbitrary bin after B and before than
or equal to F in L.
If B 0 6= Rfirst then s(B) + s(B 0 ) > 22, in particular s(B) > 11 or s(B 0 ) > 11.
If B 0 = Rfirst then s(B) + s(B 0 ) > 21.
Proof. F contains a new item n different from f . To prove (i), note that s(n) ≤ 9,
and n does not fit into B. It follows that if B ∈ E, then B must contain at least two
new items, as only items with size smaller than 9 are packed before F .
11

18

FF →

← Huge items

12
6
C

F
D

C













































































































































L MT

F

Fig. 3. A typical state of the algorithm after the second phase with regular bins. The gray (hatched) areas
denote the old items (i.e., packed in the first phase), the red (solid) regions and rectangles denote the new
items (i.e., packed in the second phase). The bins that are complete at the end of the first phase are not
shown. The item f on which the algorithm fails is shown as packed into the final bin F and exceeding the
capacity 18, following the convention introduced after Definition 2.9.

To prove (ii), let n, n0 be two new items in B 00 and note that s(B) + s(n) > 18
and s(B 0 ) + s(n0 ) > 18.
To prove (iii), observe that B 0 has a new item of size larger than 18 − s(B), and
it also has old items of size at least 3 or even 4 if B 0 6= Rfirst .
t
u
Lemma 2.11. The critical bin C is before F , there are at least two bins between C
and F and C is not in the same block as F .
Proof. All bins before C have size larger than 12. Using Lemma 2.8 we have
s(F ) + s(H) > 18 + 12|H| − 1 = 12(|H| + 1) + 5 .
It remains to bound the sizes of the other bins. Note that F 6= C as s(F ) > 18. If C
is after F , all bins before F have size more than 12, so all together s(L) > 12|L| + 5,
a contradiction. If C is just before F , then by Lemma 2.10(i), s(C) > 9 = 12 − 3
and the total size of bins in s(L) > 12|L| + 5 − 3 > 12|L|, a contradiction.
If there is a single bin B between C and F , then s(C) + s(B) plus the size of
two new items in F is more than 36 by Lemma 2.10(ii). If F ∈ E then H starts with
three bins in R, thus s(H) ≥ 12|H| + 2 using Lemma 2.8 with h = 3, and we get a
contradiction. If F ∈ R then Rfirst ∈
/ H, thus Lemma 2.8 gives s(H) ≥ 12|H|, and
we get a contradiction as well.
The last case is when C and F are in the same block with two bins between them.
Then F ∈ E, so h = 3, and C is the first bin of the three other bins from the same
block, so Rfirst ∈
/ H. Then s(C) > 9, the remaining two bins together with F have
size more than 36 by Lemma 2.10(ii) and we use s(H) ≥ 12|H| + 3 from Lemma 2.8
to get a contradiction.
t
u
We now partition L into several parts (see Figure 3 for an illustration):
Definition 2.12.
– Let F = Bi ∪ H, where F ∈ Bi .
– Let D be the set of all bins after C and before F.
12

– Let C be the set of all bins before and including C.
Lemma 2.11 shows that the parts are non-overlapping. We analyze the weight
of the parts separately, essentially block by block. Recall that a weight of a bin is
defined as w(A) = s(A) + k(A) − 13, where k(A) is the number of large and huge
items packed in A. The proof is relatively straightforward if C is not special (and
thus also F 6∈ B1 ), which is the most important case driving our choices for w. A
typical block has nonnegative weight, we gain more weight in the block of F which
exactly compensates the loss of weight in C, which occurs mainly in C itself.
Let us formalize and prove the intuition stated in the previous paragraph in a
series of three lemmata.
Lemma 2.13. If F is not in the first block then w(F) > 5, otherwise w(F) > 4.
Proof. All the new items in bins of F are large or huge. Each bin has a new item
and the bin F has two new items. Thus k(F) ≥ |F| + 1. All that remains is to show
that s(F) > 12|F| + 3, and s(F) > 12|F| + 4 if F is not in the first block.
If F is the first bin in a block, the lemma follows as s(F ) > 18 and s(H) ≥
12|H| − 1, thus s(F) = s(F ) + s(H) > 12|F| + 5.
In the remaining cases there is a bin in R ∩ F before F . Lemma 2.8 gives
s(H) ≥ 12|H|; moreover, if F ∈ E, then s(H) ≥ 12|H| + 3.
If F is preceded by three bins from F ∩ R, then F ∈ E and thus s(H) ≥ 12|H| + 3.
Using Lemma 2.10(iii) twice, two of the bins in F ∩ R before F have size at least 11
and using Lemma 2.10(i) the remaining one has size 9. Thus the size of these four
bins is more than 11 + 11 + 9 + 18 = 4 · 12 + 1, summing with the bound for H we
get s(F) > 12|F| + 4.
If F is preceded by two bins from F ∩ R, then by Lemma 2.10(i) the total size
of these two bins and two new items in F is more than 36. If F ∈ R, the size of
old items in F is at least 4 and with s(H) ≥ 12|H| we get s(F) > 12|F| + 4. If
F ∈ E, which also implies that F is in the first block, then s(H) ≥ 12|H| + 3, thus
s(F) > 12|F| + 3.
If F is preceded by one bin R from F ∩ R, then let n be a new item in F different
from f . We have s(R) + s(n) > 18 and s(f ) > 6. We conclude the proof as in the
previous case.
t
u
Lemma 2.14.
If C ∈ R then w(C) ≥ −6.
If C ∈ E then w(C) ≥ −5.
If C is a special bin then w(C) ≥ −4.
Proof. For every bin B before C, s(B) > 12 and thus w(B) > −1 by the definition
of C. Let C 0 be the set of all bins B before C with w(B) ≤ 0. This implies that for
B ∈ C 0 , s(B) ∈ (12, 13] and B has no large item. It follows that any new item in any
bin after the first bin in C 0 has size more than 5. We have
w(C) ≥ w(C 0 ) + w(C) ≥ −|C 0 | + w(C) .

(3)

First we argue that either |C 0 | ≤ 1 or C 0 = {M, T }. Suppose that |C 0 | > 1, choose
B, B 0 ∈ C 0 so that B is before B 0 . If B 0 ∈ E, either B 0 has at most two (new) non-large
13

items and s(B 0 ) ≤ 6+6 = 12, or it has at least three items and s(B 0 ) > 5+5+5 = 15;
both options are impossible for B 0 ∈ C 0 . If B 0 ∈ R, it has old items of total size in
(3, 6]. Either B 0 has a single new item and s(B 0 ) ≤ 6 + 6 = 12, or it has at least two
new items and s(B 0 ) > 3 + 5 + 5 = 13; both options are impossible for B 0 ∈ C 0 . The
only remaining option is that B 0 is a special bin. Since L has a large item, L 6∈ C 0
and C 0 = {M, T }.
By Lemma 2.10(i), we have w(C) ≥ −4. The lemma follows by summing with (3)
in the following three cases: (i) C ∈ R, (ii) if C 0 = ∅ and also (iii) if both C ∈ E and
|C 0 | = 1.
For the remaining cases, (3) implies that it is sufficient to show w(C) ≥ −3.
If C ∈ E and C 0 = {M, T } then C contains two new items of size at least 5, thus
w(C) ≥ −3. If C = T and C 0 = {M } then C either has a large item, or it has two
new items: otherwise it would have size at most 3 of old items plus at most 6 from a
single new item, total of at most 9, contradicting Lemma 2.10(i). Thus w(C) ≥ −3
in this case as well.
t
u
Lemma 2.15. (i) For every block Bi ⊆ D we have w(Bi ) ≥ 0.
(ii) If there is no special bin in D, then w(D) ≥ 0. If also C ∈ R then w(D) ≥ 1.
Proof. First we claim that for each block Bi ⊆ D with three bins in R, we have
w(Bi ) ≥ 0 .

(4)

By Lemma 2.10(iii), one of the bins in R ∩ Bi has size at least 11. By Lemma 2.10(ii),
the remaining three bins have size at least 36. We get (4) by observing that k(Bi ) ≥ 5,
as all the new items placed after C and before F are large, each bin contains a new
item and Ei contains two new items.
Next, we consider an incomplete block, that is, a set of bins B with at most two
bins from R ∩ D followed by a bin E ∈ E ∩ D. We claim
w(B) ≥ 1 .

(5)

The bin E contains two large items, since it is after C. In particular, w(E) ≥ 1 and
(5) follows if |B| = 1. If |B| = 2, the size of one item from E plus the previous bin
is more than 18, the size of the other item is more than 6, thus s(B) ≥ 24; since
k(B) ≥ 3, (5) follows. If |B| = 3, by Lemma 2.10(ii) we have s(B) ≥ 36; k(B) ≥ 4
and (5) follows as well.
By definition, D ends by a bin in E (if nonempty). Thus the lemma follows by
using (5) for the incomplete block, i.e., for C ∈ R or for B1 if it does not have three
bins in R, and adding (4) for all the remaining blocks. Note that C ∈ R implies
D=
6 ∅.
t
u
We are now ready to derive the final contradiction.
If D does not contain a special bin, we add the appropriate bounds from
Lemmata 2.14, 2.15 and 2.13. If C ∈ R then F is not in the first block and
w(L) = w(C) + w(D) + w(F) > −6 + 1 + 5 = 0. If C ∈ E then F is not in the first
block and w(L) = w(C) + w(D) + w(F) > −5 + 0 + 5 = 0. If C is the last special
bin then w(L) = w(C) + w(D) + w(F) > −4 + 0 + 4 = 0. In all subcases w(L) > 0,
a contradiction.
14

The rest of the proof deals with the remaining case when D does contain a special
bin. This implies there are at least two special bins and C is not the last special bin.
Since T is always the last special bin (if it exists), it must be the case that C 6= T
and thus C = L or C = M . We analyze the special bins together with the first block,
up to F if F belongs to it. First observe that the only bin possibly before C is L
and in that case w(L) ≥ 0, so w(C) ≥ w(C).
Let A denote F if F ∈ B1 or E1 if F 6∈ B1 . As A = F or A ∈ E, we know that A
contains at least two new items; denote two of these new items by n and n0 . Since A
is after C, we know that both n and n0 are large or huge.
Let A be the set containing C and all bins between C and A, not including A.
Thus A contains two or three special bins followed by at most three bins from R. We
have k(A) ≥ |A| − 1 as each bin in A contains a large item, with a possible exception
of C (if C = M ). Furthermore k(A) ≥ 2. The bound on k(A) and k(A) imply that
w(A) + w(A) ≥ s(A) + s(A) − 12|A| − 12

(6)

and thus it is sufficient to bound s(A) + s(A).
The precise bound we need depends on what bin A is. In each case, we first
determine a sufficient bound on s(A) + s(A) and argue that it implies contradiction.
Afterwards we prove the bound. Typically, we bound the size by creating pairs of
bins of size 21 or 22 by Lemma 2.10(iii). We also use that s(B) > 9 for any B ∈ A
by Lemma 2.10(i) and that n, n0 together with any two bins in A have size at least
36 by Lemma 2.10(ii).
Case A 6= F : Then F 6∈ B1 and A = E1 . We claim that
s(A) + s(A) ≥ 12|A| + 7 .

(7)

First we show that (7) implies a contradiction. Indeed, (7) together with (6) yields
w(A) + w(A) ≥ −5 and summing this with all the other bounds, namely w(F) > 5
from Lemma 2.13 and w(Bi ) ≥ 0 for whole blocks Bi ∈ D from Lemma 2.15, leads
to w(L) > 0, which is a contradiction.
Now we prove (7). The items n and n0 from A together with the first two special
bins in A have size more than 36. Let A0 be the set of the remaining bins; it contains
possibly T and at most three bins from R. It remains to show s(A0 ) ≥ 12|A0 | − 5.
For |A0 | = 0 it holds trivially.
If |A0 | = 1, the only bin in A0 has size more than 9 and this is sufficient.
For |A0 | > 1 we apply Lemma 2.10(iii) and pair as many bins from A0 as possible;
note that all the bins in A0 except possibly T are in R, so the assumptions of
the lemma hold. If |A0 | = 2, then s(A0 ) > 21 = 2 · 12 − 3. For |A0 | = 3 we get
s(A0 ) > 22 + 9 = 3 · 12 − 5, since we can create a pair without Rfirst . Finally, if
|A0 | = 4 then s(A0 ) > 22 + 21 = 4 · 12 − 5.
Case A = F : We claim that it is sufficient to prove


8 if F ∈ R and Rfirst ∈ A,
0
s(A) + s(n) + s(n ) > 12|A| + 9 if either F ∈ R or Rfirst ∈ A,


10 in all cases.

First we show that (7) implies a contradiction.
15

(8)

If F = E1 we note that h = 3 (as H starts with 3 bins in R). Thus Lemma 2.8,
items (iii) and (iv), together with w(H) ≥ s(H) − 12|H| yields w(H) ≥ 3 for
Rfirst ∈ A or w(H) ≥ 2 for Rfirst 6∈ A. Summing this with w(A) + w(A) > −3 or
w(A) + w(A) > −2, that are obtained from (6) and (8) in the respective cases, we
obtain w(L) > 0, a contradiction.
If F ∈ R then we know that F also contains old items of size at least 3 if Rfirst 6∈ A
or even 4 if Rfirst ∈ A (and thus F =
6 Rfirst ). Summing this with the respective bound
from (8) we obtain s(A) + s(F ) > 12|A| + 12. Summing this with s(H) ≥ 12|H|
from Lemma 2.8(iii) now yields s(L) > 12|L|, a contradiction.
Thus (7) always leads to a contradiction.
We now distinguish subcases depending on |A| and in each case we either prove (8)
or obtain a contradiction directly. Note that Rfirst ∈ A whenever |A| ≥ 4.

Case |A| = 2: The two bins together with n and n0 have size more than 36. Thus
s(A) + s(n) + s(n0 ) > 36 = 12 · 2 + 12, which implies (8).

Case |A| = 3: We have s(C) > 9 and the remaining two bins together with n and
n0 have size more than 36. Thus s(A) + s(n) + s(n0 ) > 12|A| + 9, which implies (8)
in all cases except if F = E1 and Rfirst 6∈ A.
In the remaining case, A = {L, M, T } and C = L, as A contains no bin from
R and |A| = 3. We prove a contradiction directly. Let o be the size of old items
in T . We apply Lemma 2.8(ii), using the fact that o + ρ > 6 by Lemma 2.5(v),
where ρ is the total size of old items in Rfirst ∈ H, and h = 3. We get o + s(H) ≥
o + 12|H| + h + ρ − 4 > 12|H| + 5. Let n00 be a new item in T . Since n00 does not fit into
M , s(M ) + s(n00 ) > 18; also s(L) > 9 and s(F ) > 18. Summing all the bounds, we
have s(L) ≥ o+s(H)+s(M )+s(n00 )+s(L)+s(F ) > 12|H|+5+18+9+18 = 12|L|+2,
a contradiction.
Case |A| = 4: The last bin R ∈ A is in R. Together with any previous bin it has
size more than 21, the remaining two bins together with n and n0 have size more
than 36 by Lemma 2.10(ii). Thus s(A) + s(n) + s(n0 ) > 21 + 36 = 4 · 12 + 9 which
implies (8), since Rfirst ∈ A.
Case |A| = 5: First consider the case F = E1 . The last two bins of A are in R, we
pair them with two previous bins to form pairs of size more than The remaining bin
has size at least 9, since n does not fit into it and s(n) < 9. We also have s(F ) > 18.
Thus s(A) + s(A) > 21 + 22 + 9 + 18 = 5 · 12 + 10, which implies (8).
If F ∈ R then one of the last two bins of A has size more than 11 and the
other forms a pair of size more than 21 with one special bin. The remaining two
bins together with n and n0 have size more than 36 by Lemma 2.10(ii). Thus
s(A) + s(n) + s(n0 ) > 11 + 21 + 36 = 5 · 12 + 8 which implies (8), because Rfirst ∈ A.
Case |A| = 6: Then A contains all three special bins and three bins from R, therefore
also F = E1 . We form three pairs of a special bin with a bin from R of total size more
than 21+22+22. Since s(F ) > 18, we have s(A)+s(F ) > 21+22+22+18 = 6·12+11.
Since in this case A = F = E1 , we have s(H) ≥ 12|H| + 3 and s(L) > 12|L|, a
contradiction.
In all of the cases we can derive a contradiction, which implies that our algorithm
cannot fail. This concludes the proof of Theorem 2.1.
t
u
16

3

Conclusions

We note that the analysis of our algorithm is tight, i.e., if we reduce the capacity
of the bins below 18, the algorithm fails. Consider the following instance. Send two
items of size 6 which are in the first phase packed separately into two bins. Then
send m − 1 items of size 12. One of them must be put into a bin with an item of size
6, i.e., one bin receives items of size 18, while all the items can be packed into m
bins of size 12.
To decrease the upper bound below 1.5 seems challenging. In particular, the
instance above and its modifications with more items of size 6 or slightly smaller
items at the beginning shows that these items need to be packed in pairs. This in
turns creates difficulties that, in the current approach, lead to new item and bin
types; at this point we do not know if such an approach is feasible.
Another possible research direction is to improve the lower bounds, in particular
for large m. It is quite surprising that there are no lower bounds for m > 5 larger
than the easy bound of 4/3.
Acknowledgment. The authors thank Emese Bittner for useful discussions during
her visit to Charles University. We also thank to referees for many useful comments.

References
1. S. Albers and M. Hellwig. Semi-online scheduling revisited. Theor. Comput. Sci., 443:1–9, 2012.
2. J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. On-line load balancing with applications to
machine scheduling and virtual circuit routing. J. ACM, 44:486–504, 1997.
3. Y. Azar and O. Regev. On-line bin-stretching. In Proc. of Randomization and Approximation Techniques
in Computer Science (RANDOM), pages 71–81. Springer, 1998.
4. Y. Azar and O. Regev. On-line bin-stretching. Theor. Comput. Sci. 268(1):17–41, 2001.
5. P. Berman, M. Charikar, and M. Karpinski. On-line load balancing for related machines. J. Algorithms,
35:108–121, 2000.
6. M. Böhm, J. Sgall, R. van Stee, and P. Veselý. Better algorithms for online bin stretching. In Proc. of
the 12th Workshop on Approximation and Online Algorithms (WAOA 2014), Lecture Notes in Comput.
Sci. 8952, pages 23-34, Springer, 2015.
7. M. Böhm, J. Sgall, R. van Stee, and P. Veselý. Online Bin Stretching with Three Bins. arXiv preprint
arXiv:1404.5569v3. 2016.
8. E. Coffman Jr., J. Csirik, G. Galambos, S. Martello, and D. Vigo. Bin Packing Approximation
Algorithms: Survey and Classification, In P. M. Pardalos, D.-Z. Du, and R. L. Graham, editors,
Handbook of Combinatorial Optimization, pages 455–531. Springer New York, 2013.
9. T. Ebenlendr, W. Jawor, and J. Sgall. Preemptive online scheduling: Optimal algorithms for all speeds.
Algorithmica, 53:504–522, 2009.
10. M. Gabay, N. Brauner, V. Kotov. Computing lower bounds for semi-online optimization problems:
Application to the bin stretching problem. HAL preprint hal-00921663, version 2, 2013.
11. M. Gabay, N. Brauner, V. Kotov. Improved Lower Bounds for the Online Bin Stretching Problem.
HAL preprint hal-00921663, version 3, 2015.
12. M. Gabay, V. Kotov, N. Brauner. Semi-online bin stretching with bunch techniques. HAL preprint
hal-00869858, 2013.
13. R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math., 17:263–269, 1969.
14. D. Johnson. Near-optimal Bin Packing Algorithms. Massachusetts Institute of Technology, project
MAC. Massachusetts Institute of Technology, 1973.
15. H. Kellerer and V. Kotov. An efficient algorithm for bin stretching. Operations Research Letters,
41(4):343–346, 2013.
16. H. Kellerer, V. Kotov, M. G. Speranza, and Z. Tuza. Semi on-line algorithms for the partition problem.
Oper. Res. Lett., 21:235–242, 1997.
17. K. Pruhs, J. Sgall, and E. Torng. Online scheduling. In J. Y.-T. Leung, editor, Handbook of Scheduling:
Algorithms, Models, and Performance Analysis, chapter 15, pages 15–1 – 15–41. CRC Press, 2004.
18. J. Ullman. The Performance of a Memory Allocation Algorithm. Technical Report 100, 1971.

17

