Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing.
We consider the one-dimensional bin packing problem under the discrete uniform distributions $U\{j,k\}$, $1 \leq j \leq k-1$, in which the bin capacity is $k$ and item sizes are chosen uniformly from the set $\{1,2,\ldots,j\}$. Note that for $0 < this is a discrete version of the previously studied continuous uniform distribution $U(0,u]$, where the bin capacity is 1 and item sizes are chosen uniformly from the interval $(0,u]$. We show that the average-case performance of heuristics can differ substantially between the two types of distributions. In particular, there is an online algorithm that has constant expected wasted space under $U\{j,k\}$ for any $j,k$ with $1 \leq j < k-1$, whereas no online algorithm can have $o(n^{1/2})$ expected waste under $U(0,u]$ for any $0 < u \leq 1$. Our $U\{j,k\}$ result is an application of a general theorem of Courcoubetis and Weber that covers all discrete distributions. Under each such distribution, the optimal expected waste for a random list of $n$ items must be either $\Theta (n)$, $\Theta (n^{1/2} )$, or $O(1)$, depending on whether certain ``perfect'' packings exist. The perfect packing theorem needed for the $U\{j,k\}$ distributions is an intriguing result of independent combinatorial interest, and its proof is a cornerstone of the paper. We also survey other recent results comparing the behavior of heuristics under discrete and continuous uniform distributions.
Introduction
. Suppose one is given items of sizes 1, 2, 3, . , j, one of each
size, and is asked to pack them into bins of capacity k with as little wasted space as
possible, i.e., one is asked to find a least cardinality partition (packing) of the set of
items such that the sizes of the items in each block (bin) sum to at most k. For what
Published electronically February 1, 2002. This paper originally appeared in SIAM Journal on
Discrete Mathematics, Volume 13, Number 3, 2000, pages 384-402.
http://www.siam.org/journals/sirev/44-1/39542.html
# Department of Computer Science, Athens University of Economics and Business, Athens, Greece
(courcou@csi.forth.gr).
- Bell Labs, Murray Hill, NJ 07974.
# Statistical Laboratory, University of Cambridge, Cambridge CB3 0WB, UK (R.R.Weber@
statslab.cam.ac.uk).
# Avaya Labs Research, Basking Ridge, NJ 07920 (mihalis@research.avayalabs.com).
values of j and k can the set be packed perfectly (i.e., so that the sizes of the items in
each block sum to exactly k)? Clearly the sum of the item sizes must be divisible by k,
but what other conditions must be satisfied? Surprisingly, the divisibility constraint
is not only necessary but su#cient. Readers might want to try their hand at proving
this. Relatively short proofs exist, as illustrated in the next section, but a certain
ingenuity is required to find one. The exercise serves as a warm-up for the following
more general and more di#cult theorem, also proved in the next section, in which
there are r copies of each size for some r # 1.
Theorem 1 (perfect packing theorem). For positive integers k, j, and r, with
perfectly pack a list L consisting of rj items, r each of sizes 1 through
into bins of size k if and only if the sum of the rj item sizes is a multiple of k.
In set-theoretic terms, the question answered by Theorem 1 is an intriguing puzzle
in pure combinatorics. But our motivation to work on it came from its relevance
to certain fundamental questions about the average-case analysis of algorithms. In
particular, consider the standard bin packing problem, in which one is given a bin
capacity b and a list of items each a i has a positive
size s i # b, and is asked to find a packing of these items into a minimum number
of bins.
In most real-world applications of bin packing, as in Theorem 1, the item sizes are
drawn from some finite set. However, the usual average-case analysis of bin packing
heuristics has assumed that item sizes are chosen according to continuous probability
distributions, which by their nature allow an uncountable number of possible item
sizes (see [3, 10], for example). The assumption of a continuous distribution has the
advantage of sometimes simplifying the analysis and has been justified on the grounds
that continuous distributions should serve as reasonable approximations for discrete
ones. But there are reasons to ask whether this is actually true. For example, consider
the continuous uniform distributions U(0, u], 0 < u # 1, where the bin capacity is 1
and item sizes are chosen uniformly from the interval (0, u], and the discrete uniform
distributions U{j, k}, 1 # j # k - 1, where the bin capacity is k and item sizes are
chosen uniformly from the set {1, 2, . , j}. The limit of the distributions U{mj,mk},
as m #, is equivalent to U(0, j/k] (after scaling by dividing the item sizes and
bin capacities by mk). However, in the limit, combinatorial questions such as those
addressed by Theorem 1 evaporate. This suggests that something important (and
may in fact be lost in the transition from discrete to continuous models.
The results in this paper show that this is indeed the case.
To describe the results, we need the following notation. If A is a bin packing
algorithm and L is a list of items, then A(L) is the number of bins used when A is
applied to L, and s(L) is the sum of the item sizes in L divided by the bin capacity.
Note that s(L) is a lower bound on the number of bins needed to pack L. The waste
in the packing of L by A is denoted by W A
an algorithm that always produces an optimal packing. In what follows, L n
denote a list of n items whose sizes are independent samples from a given distribution
F . The expected waste rate EW A
for an algorithm A and distribution F is defined
to be the expected value of W A (L n as a function of n. In what follows we typically
abbreviate this as simply the "expected waste." We say a distribution F is a bounded
waste distribution if EW OPT
As a consequence of Theorem 1 and a
classification theorem of Courcoubetis and Weber [11], we can prove the following.
Theorem 2. For any j, k with 1 < j < k - 1, EW OPT
This in itself does not represent a departure from the continuous model, since
U(0, u] is also a bounded waste distribution for all u, 0 < u < 1 [3, 16]. The distinction
comes when we consider "online" algorithms. In an online algorithm, items are
assigned to bins in the order in which they occur in the input list L. Each assignment
must be made without knowledge of the sizes or number of items later in the list, and
once an item is packed it cannot subsequently be moved. This mirrors many practical
situations but clearly is a substantial restriction on the power of an algorithm. In
particular, we can prove the following.
Theorem 3. If A is an online algorithm and u # (0, 1], then it cannot be the
case that E[W A
In contrast, in the discrete uniform case there is a single online algorithm that
has bounded expected waste for all the distributions U{j, k}, 1 # j < k - 1. This
is the recently discovered sum-of-squares algorithm (SS) of [12], defined as follows.
Suppose we are packing integer-sized items into bins of capacity b. When an online
algorithm packs an item x from such a list, the only thing relevant about the current
packing is the number N h of bins whose current contents total h, 1 # h # b - 1. SS
chooses the bin into which x is to be placed (either a new, previously empty bin or
one that is already partially filled but has enough room for x) so as to minimize the
resulting sum
h . Note that SS can be implemented to take O(b) time per
item [12], and so runs in linear time for any fixed bin size.
As shown in [12], algorithm SS performs well on average in a surprisingly general
sense. Let us say that a discrete distribution F is any triple (b, S, # p), where b is an
integral bin size, is a finite set of integral item sizes in the range
from 1 to b - 1, and #
rational probability vector, where p i > 0 is
the probability of item size s i and
ignore the possibility of items of
size b since such items always must start a new bin and completely fill it, leaving the
rest of the packing una#ected.) The following specialized version of the result of [12]
su#ces for our needs.
Theorem (see [12]). For any discrete distribution
Hence by Theorem 2, EW SS
The current paper is organized as follows. The proof of the perfect packing
theorem (Theorem 1) appears in section 2. Section 3 then presents the proof of
Theorem 2. We begin by describing the classification result of Courcoubetis and
Weber [11] upon which the proof depends. This result says that for any discrete
distribution F , EW OPT
must be one of #(n), #(n 1/2 ), or O(1). Which case
applies depends on the existence of certain perfect packings and is in general NP-
hard. However, Theorem 1 allows us avoid this complexity in the case of the discrete
uniform distributions U{j, k}. Theorem 3, this paper's contribution to the theory
of continuous distributions, is proved in section 4. We conclude in section 5 with a
survey of the results that have been proved about the average-case behavior of bin
packing algorithms under discrete and continuous distributions. As we shall see, there
are other significant di#erences between the discrete and continuous cases.
2. The Perfect Packing Theorem. We begin our proof of Theorem 1 with three
lemmas that list a number of special instances that lead to perfect packing. The first
lemma takes care of the special case, r = 1.
Lemma 4. Suppose m, j, and k are positive integers such that j # k and
1)/2. Then the set of j items, one each of sizes 1, . , j, perfectly packs into m
bins of size k.
Proof. The proof is by induction. Pick j and k and assume the theorem is true
for all pairs that are smaller in lexicographic order than (k, j). The theorem is clearly
true for k # 2 or j # 2, so assume k, j > 2.
then we can start by perfectly packing bins with pairs of items
(j after which the remaining items are those of sizes
plus the item of size k/2 if k is even. Since the sum of the sizes of
the items that have been packed at this point is a multiple of k, the sum of the sizes
of the remaining items is also a multiple of k. If k is odd, the unpacked items are an
instance of (k, and the induction hypothesis applies.
If k is even, then k/2 divides j(j + 1)/2 and all remaining items are no larger than
k/2. Thus the items 1, . , k - j - 1 form an instance of (k/2, k - j - 1) and by the
induction hypothesis can be perfectly packed into bins of size k/2. These half-bins
and the item of size k/2 can then be combined into bins of size k.
Now suppose j # k/2. If k is even, then we have an instance of (k/2, j) and the
induction hypothesis applies. If k is odd, first note that k/2 # j and j > 2 imply
which together with 2m. Thus we can
construct m pairs of items each of total size k
1. If we place one pair in each of our m bins, we now have
bins with gaps of size k - k items of sizes 1, . , j - 2m.
Because 1)/2, the sum of these item sizes must be m(k - k # ), and so an
application of the induction hypothesis to the instance completes the
proof.
Lemma 5. Consider r > 1 sets, the ith of which consists of j items of consecutive
(a) r is even or (b) j is odd.
Then these rj items perfectly pack into j bins of size equal to the sum of the average
item sizes in the r groups, i.e., r(j
Proof. The lemma will follow if we can show that for # bins
of size r(j + 1)/2 it is possible to pack perfectly the items into the j bins in such a
manner that each bin contains exactly one item from each of the r sets.
If r is even, then we simply take two of the sets and pack the ith largest item
in one set with the ith smallest item in the other set, i.e., as the pair (i,
bins to level j + 1. By repeating this r/2 times we fill j bins
of size r(j + 1)/2.
If r and j are both odd, then an extra step is required. The idea is first to pack
items in triples, one item from each of three sets, such that the sum of each triple is
the same. It is easiest to appreciate the construction by considering an example, say
9. The triples, which each sum to 15, are given in the columns below.
In general, the triples are (i, i
j. The result of packing these one per
bin is to fill all j bins to level 3(j 1)/2. The number of remaining sets is even and
the remaining spaces in the j bins are equal. Thus, the procedure for case (a) can be
applied to complete the packing in each bin.
The following lemma provides part of the induction step used in the proof of
Theorem 1.
Lemma 6. Consider a quadruple (k, j, r, m) of positive integers such that k # j
and 1)/2. Then there exists a perfect packing of r copies of 1, . , j
into m bins of size k if there exists a perfect packing for each lexicographically smaller
quadruple of this form, and if any one of the following holds:
(b) r does not divide k.
(c) k or r is even.
Proof. First, using the arguments of Lemma 4, we demonstrate how to reduce the
problem to a smaller instance if (a) holds. If j # k/2 and k is odd, then we can pack
bins with pairs (j - 1)/2. The remaining items, which
are of sizes 1, . , k - j - 1, define the smaller instance (k, k -
and k is even, then we can pack bins in the same
way, k/2. The remaining items, which are of sizes 1, . ,
and k/2, can be packed into bins of size k/2 by the induction hypothesis that there
exists a perfect packing for
If (b) holds, then r and m must have a common factor p > 1 and the problem
reduces to the instance (k, j, r/p, m/p).
Now suppose neither (a) nor (b) holds but (c) does. If k is even, then k/2 divides
k/2. Thus the problem reduces to a smaller
instance in which the bin size is k/2. If r is even, then since (b) does not hold, k is
divisible by r and so must be even too. Thus the same argument applies.
Finally, for case (d), assume that (a), (b), and (c) do not hold, i.e., j < k/2, r
divides k, and k and r are both odd. Let r
k. The fact that r is odd implies that
r 1 and r 2 are integers. The fact that r divides k implies that k 1 and k 2 are integers,
with 1)/2. Since by assumption j < k/2, we
have hence by hypothesis for the instance (k 1 , j, r 1 , m), we can pack r 1
copies of 1, . , bins of size k 1 . Similarly, if also then we can pack
copies of 1, . , bins of size k 2 . Since we can combine pairs
of bins of sizes k 1 and k 2 into bins of size k. Thus there is a reduction to smaller
instances holds.
Proof of the perfect packing theorem. Instances for which the theorem is to be
proved are described by the quadruples of Lemma 6. Notice that it would be enough
to specify the triple (k, j, r); however, it is helpful to mention m explicitly. The proof
of the theorem is by induction on (k, j, r) under lexicographical ordering. By Lemma 4
it is true for 1. Assume all quadruples that are smaller than (k, j, r, m) can be
perfectly packed and r > 1. We show there exists a perfect packing of r copies of
1, . , bins of size k. By Lemma 6, we need only consider the case when
and r are odd, r divides k, and (r - 1)k/2r < j < k/2. Note that in this case
(r - 1)k/2r is an integer and k/2r is 0.5 more than an integer. We show below that
we can perfectly pack all the items of sizes from
bins of size k. (Note that the lower bound on this range is greater than 1 because
of the above lower bound on j.) The theorem then follows because the remaining
items form a smaller quadruple, so by the induction hypothesis they can be perfectly
packed into bins of size k.
To follow the construction below, the reader may find it helpful to consider a
specific example. Consider the quadruple (k, j, r, m) = (165, 77, 5, 91). Note that k
and r are odd, r divides k, and j lies between (r -
show below how to perfectly pack all items of sizes 12, . , 77. The remaining items
form the smaller quadruple (165, 11, 5, 2).
To pack all items of sizes from j +1-(r-1)k/2r through j, we divide the range of
item sizes into intervals, i.e., sets of consecutive integers. Each interval is symmetric
about a multiple of k/2r and has one of two lengths depending on whether the interval
100 COFFMAN ET AL.
is symmetric about an odd or even multiple of k/2r. To form the intervals, we first
take the largest interval that is symmetric about (r - 1)k/2r; this is the interval
[(r -1)k/r-j, j]. Note that this interval does not include (r -2)k/2r since j <
rk/2r. Next we take the largest interval that can be formed from the remaining items
that is symmetric about (r-2)k/2r, obtaining the interval [j-k/r+1, (r-1)k/r-j-1].
Continuing in this fashion and taking intervals symmetric about further multiples of
k/2r, we end up with intervals of two kinds. First, there are (r - 1)/2 intervals
centered on even multiples of k/2r, with the interval centered on (r - 1 - 2i)k/2r
being ranges from 0 to (r - 3)/2. Second, there
is an equal number of intervals centered on odd multiples of k/2r, with the interval
centered on (r - 2i)k/2r being [j - ik/r ranges from 1
to (r - 1)/2. Note that the smallest endpoint is
claimed above.
For the numerical example above, there are two intervals of each type. Intervals
of the first type are [22, 44] and [55, 77]; they are of length 23 and symmetric about 33
and 66. Intervals of the second type are [12, 21] and [45, 54]; they are of length 10 and
symmetric about 16.5 and 49.5. In general, intervals of the first type have odd length
are symmetric about an even multiple of k/2r. Intervals of
the second type have even length k -2j -1 and are symmetric about an odd multiple
of k/2r. Our plan is to use Lemma 5 to perfectly pack into bins of size k those items
whose sizes lie in intervals of the same type.
We begin by considering all those intervals of the first type. These have odd
lengths and they are symmetric about points ik/r, 1)/2. There are
r items of each size in each of these intervals. Our strategy is to partition these
intervals into groups that satisfy the hypotheses of Lemma 5(b). That is, we arrange
for the midpoints of the intervals within each group to sum to k. Since the midpoints
correspond to the average item sizes for the corresponding intervals, and the number
of items in the intervals is odd, Lemma 5(b) implies that we can perfectly pack the
items in the intervals of each group. Constructing these groups is a bin packing
problem in which the midpoints of the intervals take on the role of item sizes. In
what follows we write "items" in quotes when speaking of the midpoints of intervals,
possibly normalized, and viewing them as items to be perfectly packed in bins of
some required size. In considering intervals of the first type, it is as though we had
r "items" of each of the sizes ik/r, and wished to pack them
into bins of size k. After a normalization that multiplies each item size by r/k, this is
equivalent to the problem of packing r "items" of each of the sizes 1, . , (r -1)/2 into
bins of size r. That is, we have a smaller version our packing problem,
with But by the induction
hypothesis this means that the desired packing can be achieved. In the example, it is
as though we had 5 "items" of sizes 33 and 66 that are to be packed in bins of size 165.
Normalizing by a factor of 1/33, this is equivalent to the problem instance (5, 2, 5, 3).
We must now pack items whose sizes lie in intervals of the second type. These
intervals are of even length, symmetric about the points ik/2r, for i odd and
1, . , r - 2. Again, there are r items of each size in these intervals. As above, we
exhibit a reduction to a smaller perfect packing problem. After we multiply item
sizes by 2r/k the problem is equivalent to perfectly packing r copies of "items" of
sizes 1, 3, 5, . , r - 2 into bins of size 2r. For the example, this is 5 copies of "items"
of sizes 1 and 3, to be perfectly packed into 2 bins of size 10. Unfortunately, if the
sum of the "item" sizes is an odd multiple of r the "items" cannot be perfectly packed
into bins of size 2r. For this reason, and also because it is convenient to do so even
when the sum of the "item" sizes is a multiple of 2r, we consider perfect packings
into bins of sizes r and 2r. Assume for the moment that r copies of "items" of sizes
can be perfectly packed into bins of sizes r and 2r. If they are packed
entirely into bins of size 2r, then the number of "items" in each bin must be even (as
all "item" sizes are odd), and so Lemma 5 applies and implies that the original items
can be perfectly packed into bins of size k. On the other hand, suppose a bin of size r
is required. The set of "items" that are packed into a bin of size r corresponds to a set
of intervals whose midpoints sum to k/2. Recall that the intervals are of even length.
We divide each such interval into its first half and its second half, obtaining twice as
many intervals, whose midpoints now sum to k. Now we can again use Lemma 5 to
construct the perfect packing.
The final step in the proof is to show that we can indeed perfectly pack r copies
of each of the item sizes 1, 3, 5, . , r - 2 into bins of sizes r and 2r. We shall use a
di#erent packing depending upon whether
For the case the "items" are perfectly packed by the following simple
procedure. We begin by packing one bin with (1, 1, r - 2), one bin with (2i
1, r-2i-2, r-2i) for each one bin with (2i-1, 2i+1, r-2i, r-2i)
for each (noting that in the final case, when #, we get three "items"
of size 2i This packs four "items" of each size larger than 1, and three
"items" of size 1. We can apply this packing # times, leaving us with one "item"
of each size larger than 1 and # "items" of size 1. Then we pack one bin with
This uses up all the remaining "items" (where
#+1 items of size 1 are used because there are two "items" of size 1 when 1). For
the numerical example, in which construction says that we should pack 5
copies of 1 and 3 into bins of size 5 and 10 by first packing one bin with (1, 1,
then one bin with (1, 3, 3, 3). This leaves one "item" of size 3 and two of size 1. These
perfectly pack into a bin of size 5.
When the procedure is very similar to that above. We begin by
packing one bin with (1, 1, r - 2), one bin with (2i +1, 2i+1, r -2i-2, r -2i) for each
As
before, this packs four "items" of each size larger than 1, and three "items" of size 1.
We apply this packing # times, leaving us with three "items" of each size larger than
1 and #+ 3 "items" of size 1. Then we pack one bin with (2i - 1, 2i
for each This leaves us with # "items" of size 1, two "items" of size
one "item" of each other size. Finally, as before, we pack one bin with
uses up all remaining items.
3. Proof of Theorem 2. Recall the theorem statement: For any distribution
U{j, k}, with j < k - 1, EW OPT
We rely on a general result of Courcoubetis and Weber [11]. Suppose
is a discrete distribution as defined in section 1. Note that a packing of items with
sizes from into a bin of size b can be viewed as a nonnegative integer
vector
interest are those vectors
that give rise to a sum of exactly b, which we shall call perfect packing configurations.
For instance, if one such configuration would be (1, 0, 2).
Let P S,b denote the set of all perfect packing configurations for a given S and b. Let
# S,b be the convex cone in R d spanned by all nonnegative linear combinations of
configurations in P S,b .
Theorem (Courcoubetis and Weber [11]). For any discrete distribution
(b, S, # p), the following hold.
(a) If # p lies in the interior of # S,b , then EW OPT
(b) If # p lies on the boundary of # S,b , then EW OPT
(c) If # p lies outside of # S,b , then EW OPT
In general it is NP-hard to determine which of the three cases applies to a given
distribution (as can be proved by a straightforward transformation from the PARTITION
problem [13]). However, for the distributions U{j, k}, j < k - 1, we can use
the following lemma, which we shall prove using the perfect packing theorem, to show
that (a) applies.
Lemma 7. For each i, j, k with exist positive integers
such that the set of r items consisting of r items of size i
together with r i items of each of the other j - 1 sizes can be packed perfectly into m i
bins of size k.
Note that this lemma implies that the j-dimensional vector -
is strictly inside the appropriate cone when 1. This is
because -
e is in the interior of the cone spanned by vectors of the form (r i , . , r
those vectors are sums of perfect packing configurations
by Lemma 7. The proof of Theorem 2 thus follows from case (a) of the above theorem.
Proof of Lemma 7. We make use of the perfect packing theorem. There are two
cases. If k we simply set r
that the total size of r i items each of the sizes 1, . , so by the
perfect packing theorem, we can perfectly pack them into j(j bins of size
i. The remaining s items of size i can then go one per bin to fill these
bins up to size precisely k.
On the other hand, suppose Now things are a bit more complicated.
We have r 1)/2. By
the perfect packing theorem r i items each of the sizes 1, . , perfectly pack
in s i bins of size k - i. (Such items exist because by assumption j < k - 1.) We
then add the additional s i items of size i to these bins, one per bin, to bring each
bin up to size k. There remain r i items each of sizes k - j through j, for a total of
items. These can be used to completely fill the remaining
bins with pairs of items of sizes (j, k - j), (j - 1, k
Note that if k is even, the last bin type contains two items of size k/2, but we have an
even number of such items by our choice of r presents no di#culty.
It is easy to verify that in both cases r i , s i , and m i are all less than 2k 2 .
4. Proof of Theorem 3. Recall the theorem statement: If L n has item sizes
generated according to U(0, u] for 0 < u # 1, and A is any online algorithm, then
there exists a constant c > 0 such that E[W A (L n )] > cn 1/2 for infinitely many n.
Proof. Let w(t) denote the amount of empty space in partially filled bins after t
items have been packed. We show that for any n > 0 the expected value of the average
of w(1), . , w(n) is # n 1/2 u 3 ). This implies that E[w(n)] must
be# (n 1/2 u 3 ), i.e.,
not o(n 1/2 ).
Consider packing item a t+1 . Let #(t) denote the number of nonempty bins that
have a gap of at least u 2 /8 after the first t items have been packed. There are at most
bins into which one can put an item larger than u 2 /8. Therefore, if a t+1 is to
leave a gap of less than # in its bin, either it must have size less than u 2 /8 or its size
must be within # of the empty space in one of these #(t) bins with gaps larger than
/8. The probability of this is at most [u 2 /8+#(t)]/u. By choosing
conditioning on whether #(t) is greater or less than n 1/2 , and noting that the size of
a t+1 is distributed as U(0, u] independent of #(t), we have
Now
(a s+1 is last in a bin and leaves gap #)
[P (a s+1 is last in a bin)
- P (a s+1 is last in a bin and leaves gap < #)]
[P (a s+1 is last in a bin) - P (a s+1 leaves gap < #)]
(a s+1 is last in a bin) -
u/4.
t be the sum of the first t item sizes, and note that S t is a lower bound on
the number of bins and hence on the number of items that are the last item in a bin.
We thus have
(a s+1 is last in a bin) # E[S t
Using the fact that we then have
If
we have for all t # n/2,
This implies
On the other hand, if
w(t) #n
These imply that E[w(n)]
is# (n 1/2 ).
It should be noted that the above proof relies heavily on the fact that the distribution
is continuous, since this is the reason why the union of n 1/2 intervals of size
cannot cover the full probability space. Our discrete distributions U{j, k} do not
have this failing, and for this reason we can obtain significantly better average-case
behavior for them.
104 COFFMAN ET AL.

Table

Expected waste in the symmetric case.
BF #(n 1/2 log 3/4 n) [26] #(n 1/2 log 3/4
Best online #(n 1/2 log 1/2 n) [26, 27] #(n 1/2 log 1/2
The upper bound is proved in the reference; the lower bound is conjectured based on experiments.
# The upper and lower bounds here appear to follow from the corresponding results for the continuous
case, but the details of the upper bound in particular still need to be worked out.
5. Concluding Remarks. The results in this paper were among the first to be
obtained about the average-case behavior of bin packing algorithms under discrete
distributions. Since they were announced in [4], many additional results have been
proved, illustrating further contrasts with (and similarities to) the case of continuous
distributions. In this concluding section we survey the literature and point out some
of the remaining open problems.
Let us begin by considering symmetric uniform distributions, as represented by
U(0, 1] and U{k - 1, k}, k # 1. (In general, a symmetric distribution is one that
satisfies p(s #) = p(s # b - #) for all #, 0 # b.) Table 1 summarizes what
is known about average-case behavior under these distributions. A horizontal line
separates the o#ine algorithms from the online ones. Except where noted, all results
in this table are theorems.
Four famous classical algorithms have been extensively studied. First fit (FF ) is
an online algorithm in which each item is placed in the first bin that has room for
it, where bins are sequenced according to the order in which they received their first
item. If no bin has room, a new bin is started. Best fit (BF ) is similar, except now
the item is placed in the bin with the smallest gap large enough to contain it (ties
broken in favor of the earlier bin). First fit decreasing (FFD) and best fit decreasing
(BFD) are the corresponding o#ine algorithms in which the list is first sorted so that
the items are in nonincreasing order by size, and then FF (BF ) is applied. From a
worst-case point of view, FF and BF are equivalent: in an asymptotic sense each can
produce packings that use 70% more bins than optimal, but neither can do any worse
[15]. The corresponding o#ine versions FFD and BFD each can use
more bins than optimal but can do no worse [14, 15].
The results in Table 1 show that these algorithms perform much better on average
than in the worst case, since they now have sublinear expected waste, a surprise when
it was first observed empirically in [2]. The o#ine versions continue to have an
advantage over their online counterparts, but it is of reduced practical significance.
And now there is a distinction in the behavior of FF and BF , with BF being the
better of the two.
The above remarks apply equally well to the discrete and continuous cases. As
to the comparison between these cases, we once again have a significant di#erence for
online algorithms. For any fixed value of k, the online algorithms in the table all have
expected waste, in contrast to the expected wastes in the continuous case of
#(n 2/3 ) for FF , #(n 1/2 log 3/4 n) for BF and #(n 1/2 log 1/2 n) for the best possible
online algorithm. (Here the notation #(f(n)) means that the lower bound is taken in
the Hardy and Littlewood sense of "not o(f(n))," i.e., "greater than cf(n) for some

Table

Possibilities for expected waste in the nonsymmetric case.
OPT #u (1) [3] # k (1) [.]
online# u (n 1/2 ), Ou (n 1/2 log 3/4 n) [.] [25] # k (1) [.]
. Results proved in this paper.
ruled out by theorems, but no occurrences are known either. For BFD and FFD,
it does not occur for any k # 10,000 [5].
# This is conjectured to hold for all u # (0, 1), based on experimental studies. To date it has been
proved only for u # [0.66, 2/3) and BF [18].
c > 0 and infinitely many n," rather than in the standard Knuthian sense of "greater
than cf(n) for some c > 0 and all su#ciently large n.")
In a sense, however, the online results for the discrete case are consistent with
those for the continuous one. Although technically an online algorithm is not allowed
to know the magnitude of n, if one formally sets in the formulas for expected
waste for the discrete case, one gets EW A
BF , and the best possible online algorithm. SS is not applicable to continuous
distributions, but note that in this asymptotic discrete sense it appears to be worse
than FF and BF . Indeed, experiments suggest that EW SS
Let us now turn to the nonsymmetric distributions U(0, u], u < 1, and U{j, k},
1. The known results for these distributions are summarized in Table 2.
Here for the first time we see di#erences between the continuous and discrete cases
for o#ine algorithms. In particular, for A # {FFD,BFD}, EW A
for all u # 1/2 [3, 16], but for many of the distributions U{j, k} with j # k/2 (the
corresponding discrete uniform distributions), we have EW A
Moreover, for u # (1/2, 1), EW A
growth rate never
occurs for U{j, k}. This follows from a theorem in [5] that says that for all discrete
distributions F , EW FFD
must be either O(1), #(n 1/2 ), or #(n).
The theorem also provides algorithms that determine the answers for a given
distribution (b, S, # p), find the constants of proportionality when the expected waste is
linear, and run in time polynomial in b and |S|. Unfortunately, although the answers
for the distributions U{j, k} with k # 10,000 have all been computed [5], these do
not suggest any simple rule as to how the choice among O(1), #(n 1/2 ), and #(n)
might depend on j and k. (As an example of the type of behavior that can occur,
for the U{j, 151} distributions the choice between linear and bounded expected waste
switches back and forth 10 times as j increases from 1 to 149.) The results for k #
10,000 do, however, exhibit several suggestive patterns. First (and this can be proved
to hold for arbitrarily large k), the expected waste is O(1) whenever j < # k or
expected waste #(n 1/2 ) does not occur for any U{j, k} with
suggesting that it may never occur. Third, for each U{j, k} with
(U{j, k}) are either both linear or both
bounded. If linear, the constant of proportionality for BFD is never larger than that
for FFD (but is occasionally smaller).
Here again there is a sense in which the discrete case is asymptotically consistent
with the continuous case, even though the expected waste for FFD and BFD is
always sublinear in the latter. As k increases, the maximum constants of proportionality
for the linear expected waste under U{j, k} appear to decrease. Indeed, it can be
106 COFFMAN ET AL.
shown that the constants for FFD are bounded by a function that declines at least
as fast as (log k)/k [5]. (This presumably holds for BFD as well.) The worst case is
the distribution U{6, 13}, for which the expected waste for both FFD and BFD is
n/624, which is less than 0.6% of the expected optimal number of bins. Moreover,
this is easily avoided, since not only does SS have bounded expected waste for this
distribution, but so do FF and BF (although this is the only case we have identified
where the online FF and BF algorithms outperform their o#ine cousins).
Turning now to the online algorithms FF and BF , we observe that their behavior
under discrete uniform distributions appears empirically to be similar to their behavior
under continuous ones. Based on extensive experiments, it is conjectured that FF
and BF both have linear expected waste under U(0, u] for 0 < u < 1, although to date
this has been proved only for u # [0.66, 2/3) and BF [18]. In the discrete case (U{j, k}
with experiments suggest that for su#ciently large k, the expected waste
for FF and BF is bounded when
linear. Some of this has been proved. In [19] it was shown that EW BF
0, and this result was extended to FF in [1]. In [4] it was
shown that EW FF
In practice, bounded expected waste is more common, at least for small k.
The growth rates for BF under U{j, k} with k # 11 were completely characterized
using multidimensional Markov chain arguments in [8], and linear expected waste only
occurs for U{8, 11}. The only general result proving linear expected waste mirrors
the result for the continuous case: EW BF
k is su#ciently large [18]. At this point we do not know if expected wastes other
than O(1) and #(n) are possible for FF or BF under any distributions U{j, k} with
classification theorem such as those for FFD, BFD, or OPT
has been proven, so the range of possibilities is not known to be limited to O(1),
#(n 1/2 ), and #(n), as it was for FFD and BFD.
There is also a gap between the lower bound proved in this paper on the best
possible online expected waste for continuous distributions U(0, u] and the best rate
known to be achievable. The former
is# (n 1/2 ) and the latter is O(n 1/2 log 3/4 n), as
proved in [25]. The algorithm of [25] works for any distribution, discrete or continuous,
but has drawbacks from a pragmatic point of view: the best current bound we have
on its running time is O(n 8 log 3 n) [12]. If one is willing to consider more specialized
algorithms, better running times are possible, at least theoretically. For any fixed
distribution F , there is an algorithm AF that runs in time O(n log n) and again
has expected waste of O(n 1/2 log 3/4 n) [24]. These algorithms have drawbacks too,
however, since the proof that they exist is nonconstructive. The question of whether
practical algorithms exist that attain these bounds, or indeed whether
lower bound is achievable, remains open.
Finally, in addition to the open problems mentioned above for the discrete and
continuous uniform distributions U(0, u] and U{j, k}, there is the question of what
happens for arbitrary discrete and continuous distributions. In the discrete case, the
above-mentioned classification theorems apply for BFD, FFD, and OPT , and say
that the corresponding expected waste must be O(1), #(n 1/2 ), or #(n). As also mentioned
above, the applicable cases for BFD and FFD and any specific distribution
can be determined in time polynomial in b and |S|. For OPT there is
also an algorithm for determining which case applies, as noted in [12]. This involves
solving up to |S| +1 linear programs with |S|b variables and |S| constraints. None
of these algorithms technically runs in polynomial time since b may be exponentially
larger than its contribution to instance size (log b). However, all are feasible for b in
PERFECT PACKING THEOREMS 107
excess of 1,000, which makes it possible to characterize the behavior of FFD, BFD,
and OPT for many interesting distributions on a case-by-case basis.
The theorem about SS presented in section 1 can be generalized to arbitrary
discrete distributions if one replaces SS by a simple variant SS # : As in SS, items
are packed so as to minimize
h , but now the choice must be made subject to
the following additional constraint: No item may be placed in a partially filled bin if
the resulting gap cannot be exactly filled with items whose sizes have already been
encountered in the list L. The resulting algorithm still runs in time O(nb) and satisfies
distributions F [12]. In addition, there
is a more complicated randomized variant that runs in time O(nb log b), satisfies the
above property, and also has the same constant of proportionality as OPT when the
expected waste is linear [12].
As to the case of arbitrary continuous distributions, we as yet have no general
classification theorems, although some partial results have been proved. Rhee
[22] provided a complicated measure-theoretic characterization of those F for which
is sublinear, but this does not appear to be computationally useful. A
result of Rhee and Talagrand [23] implies that if EW OPT
must be
O(n 1/2 ) or better. Rates strictly between O(1) and #(n 1/2 ) have not yet been ruled
out, however. Moreover, there is as yet no algorithm with the general e#ectiveness
of SS and its variants. The results of [24, 25] imply that there are online algorithms
whose expected waste is at most O(n 1/2 log 3/4
n) worse than the optimal expected
waste. For o#ine algorithms, Karmarkar and Karp have devised an algorithm which in
the worst case never uses more than the optimal number of bins plus O log 2 (OPT
O(log 2 n) [17]. This means that its expected waste is never more than the maximum of
O(log 2 n) and EW OPT
the algorithms of [24, 25], however, it is impractical,
having a running time for which our best current bound is O(n 8 log 2 n).
To conclude with an open problem that hearkens back to the main result of this
paper, note that our ability to determine the expected waste for FFD, BFD, and
OPT on a case-by-case basis can only take us so far, and more general results would be
desirable. Results for U(0, 1] and U{k - 1, k} typically continue to hold for arbitrary
continuous and discrete symmetric distributions, respectively, but the real world is
not dominated by symmetric distributions. It would be nice if we could identify
additional interesting classes of nonsymmetric distributions F for which general results
about EW OPT
can be proved, as we did in this paper for the discrete uniform
distributions. Are there interesting classes for which new perfect packing theorems
can provide us with similar general answers?



--R


An experimental study of bin packing
Some unexpected expected behavior results for bin packing







Stability of on-line bin packing with random arrivals and long-run average constraints
On the sum-of-squares algorithm for bin packing
Computers and Intractability: A Guide to the Theory of NP-completeness


Average Case Behavior of First Fit Decreasing and Optimal Packings for Continuous Uniform Distributions U(0

Linear waste of best fit bin packing on skewed distribu- tions
stochastic analysis of best fit bin packing

An Average-Case Analysis of Bin Packing with Uniformly Distributed Item Sizes
Optimal bin packing with items of random sizes
Optimal bin packing with items of random sizes.


The average case analysis of some on-line algorithms for bin packing
How to pack better than Best Fit: Tight bounds for average-case on-line bin pack- ing
--TR

--CTR
Janos Csirik , David S. Johnson , Claire Kenyon , James B. Orlin , Peter W. Shor , Richard R. Weber, On the Sum-of-Squares algorithm for bin packing, Journal of the ACM (JACM), v.53 n.1, p.1-65, January 2006
approximation algorithms;bin packing;average-case analysis;online