E.G. Coffman, Jr., D.S. Johnson, P.W. Shor

AT&T Bell Laboratories

and

G.S. Lueker

University of California at Irvine

In the last 10 years, there have been major advances in the average-case analysis of bin packing, scheduling, and similar partitioning problems in one and two dimensions. These problems are drawn from important applications throughout industry, often under the name of stock cutting. This chapter briefly surveys many of the basic results, as well as the probabilistic methods used to obtain them. The impact of the research discussed here has been twofold. First, analysis has shown that heuristic solutions often perform extremely well on average, and hence can be recommended in practice, even though worst-case behavior can be quite poor. Second, the techniques of applied probability that have developed for the analysis of bin packing have found application in completely different arenas, e.g., statistics and stochastic models.

Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.

Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter.
Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.

OCR for page 87

Probability and Algorithms
7.
Probabilistic Analysis of Packing and Related Partitioning Problems
E.G. Coffman, Jr., D.S. Johnson, P.W. Shor
AT&T Bell Laboratories
and
G.S. Lueker
University of California at Irvine
ABSTRACT
In the last 10 years, there have been major advances in the average-case analysis of bin packing, scheduling, and similar partitioning problems in one and two dimensions. These problems are drawn from important applications throughout industry, often under the name of stock cutting. This chapter briefly surveys many of the basic results, as well as the probabilistic methods used to obtain them. The impact of the research discussed here has been twofold. First, analysis has shown that heuristic solutions often perform extremely well on average, and hence can be recommended in practice, even though worst-case behavior can be quite poor. Second, the techniques of applied probability that have developed for the analysis of bin packing have found application in completely different arenas, e.g., statistics and stochastic models.

OCR for page 87

Probability and Algorithms
7.1 Introduction
7.1.1 Problems
The problems studied here all involve the partitioning of a set of positive numbers into a collection of subsets satisfying a sum constraint. The following two problems are among the most fundamental. They have wide-ranging applications throughout computer science and operations research (see, e.g., Coffman et al., 1984b; Coffman et al., 1988; and Dyckhoff, 1990).
Bin Packing (BP). Given c > 0 and a set S = {X1, ..., Xn} with , , partition S into a minimum number of subsets such that the sum of the Xi's in each subset is no more than c.
The Xi's are usually called items or pieces and are thought of as being packed into bins B1, B2, ..., each with capacity c; the items packed in a bin constitute one of the subsets in a solution to the optimization problem.
Multiprocessor Scheduling (MS). Given an integer and a set S = {X 1, ..., Xn}, partition S into m subsets such that among all such partitions, the maximum subset sum is minimized.
Note that the MS problem is complementary to the BP problem in that the objective function and the given parameter are interchanged. The items are now called tasks or jobs, with running times or durations instead of sizes. The bins become processors P1, ..., Pm, and the partition becomes a schedule of S on m processors that minimizes the makespan c, i.e., the completion time of a latest finishing task. Because of the sequential nature of most heuristics, it is convenient to assume that the set to be partitioned is given as a list Ln = (X1, ..., Xn) from which items are packed or scheduled one by one. If H denotes an MS heuristic, then H(Ln, m) denotes the makespan of the m-processor schedule generated by H for the tasks in Ln. In the BP problem the bin capacity is only a scale factor, so we take c = 1 without loss of generality. Thus, if H denotes a BP heuristic, then H(Ln) denotes the number of unit capacity bins in which H packs the items of Ln.
Merely deciding whether a list of numbers can be partitioned into two subsets with equal sums is NP-complete, so, as one would expect, both the BP and the MS problems are NP-complete. Thus, one is unlikely to find an

OCR for page 87

Probability and Algorithms
algorithm that will solve these problems exactly and efficiently.1 For this reason, a large literature has built up over the past 20 years on the design and analysis of heuristic or approximation algorithms. Such algorithms are designed to generate optimal or nearly optimal solutions for most problem instances. Quantifying this last statement is the goal of analysis.
7.1.2 Analysis
Early research on BP, MS, and related problems concentrated on combinatorial, worst-case results, as reflected in the survey by Coffman et al. (1984b). For example, a scheduling heuristic H would be assessed by determining for each m a least upper bound over all Ln, and n on the ratio H(Ln, m)/OPT(Ln, m), where OPT stands for an optimal algorithm; i.e., OPT(Ln, m) denotes the makespan of a solution to the MS problem for the problem instance (Ln, m). Similarly, the ratios H(Ln)/OPT(Ln) were bounded for BP heuristics H. Such results are inherently pessimistic, so probability models were introduced in order to learn more about the probable or average-case behavior of heuristics.
Probabilistic analysis began about 10 years ago and gained considerable momentum when some striking new results were developed a few years later. In the standard probability model, the Xi's are taken as independent samples of a random variable X with a given distribution F(x). The goal is then an estimate of distributions such as , or what is sometimes easier to obtain, expected values such as E[H(Ln, m)], where the expectations are over all n-item samples Ln = (X1, ..., Xn).
Typically, exact analysis of probability models is quite difficult, especially for the more efficient algorithms, so asymptotic techniques have been used. These techniques estimate behavior for large problem instances, i.e., for large n. Also, the estimates often take the form of expressions with terms that are precise only within unspecified multiplicative constants. For example, let F(x) be the uniform distribution on [0,1]. Then as illustrated later, there are BP heuristics H for which it has been proved that . Here, the Θ(·) notation is simply a relaxation of the concept ''is proportional to." Precisely, f(n) = Θ(g(n)) means that there exist constants α, β > 0 such that for all n large enough,
1
For a comprehensive treatment of NP-completeness and its implications, see Garey and Johnson (1983).

OCR for page 87

Probability and Algorithms
If we only know the existence of β > 0 such that the right-hand inequality is satisfied for all n large enough, then we write the familiar f( n) = O(g(n)). A similar restriction to α and the left-hand inequality is denoted f(n) = Ω(g(n)).
We emphasize that usually very little is known about the multiplicative constants hidden in the Θ(·) terms. One can almost always find some bounds for these constants, but in most cases there is reason to believe that the bounds are very crude.
In the remainder of this section, we present a number of fundamental algorithms together with a sampling of results that measure the quality of the packings or schedules produced.
7.1.3 Bp Algorithms
We begin by describing three algorithms that pack the items in the sequence X1, ..., Xn. An item is packed when it is encountered; once packed, it is not moved thereafter. The algorithms are said to be on-line because, for each i, , the rule that decides where Xi is packed is independent of the number and sizes of the remaining items Xi+1, ..., Xn. All three algorithms begin by packing X1 into B1.
The simplest of the three algorithms is next fit (NF). In packing Xi, , NF first checks the highest-indexed, nonempty bin, say Bj, . Xi is packed in Bj if it fits, i.e., if Xi plus the sum of the items already packed in Bj is at most 1. Otherwise, Xi is packed into Bj+1, which then becomes the new highest-indexed, nonempty bin.
The two algorithms, first fit (FF) and best fit (BF), improve on NF by checking all nonempty bins before starting a new bin; i.e., FF and BF pack am item Xi into an empty bin if and only if Xi does not fit into any nonempty bin. FF packs Xi, , into the lowest-indexed nonempty bin, if any, in which Xi fits, and BF packs Xi into a nonempty bin, if any, in which Xi fits best, i.e., with the least unused capacity left over. Ties are resolved by BF in favor of lower-indexed bins.
Improved, off-line versions of these algorithms are obtained by first sorting the Xi's into decreasing order; the corresponding NFD, FFD , and BFD algorithms (D stands for decreasing) are simply NF, FF, and BF applied to the list (X(n)), ..., X(1)), where X((i)) denotes the ith smallest item in Ln.
Table 7.1 summarizes a number of the basic results that have been derived for the above algorithms under the assumption X ~ U(0, 1); i.e., F(x) is the uniform distribution on [0, 1]. The performance metric shown is the

OCR for page 87

Probability and Algorithms
TABLE 7.1: Analyses of Bin Packing Algorithms
Assumption: X ~ U(0, 1)
Next Fit:
Coffman et al. (1980)
First Fit: E[WFF(Ln)] = Θ(n2/3)
Shor (1986) and Coffman et al. (1991)
Best Fit:
Shor (1986)
Next Fit Decreasing:
E[WNFD(Ln)] = (.145 ...)n
Hofri and Kamhi (1986) and Csirik et al. (1986)
First Fit Decreasing (FFD), Best Fit Decreasing (BFD), and Optimal (OPT):
for H = FFD (Bentley et al, 1984)
BFD, or OPT (Lueker, 1982)
expected wasted space,
where σ(Ln) denotes the sum of the item sizes in Ln. Note that FF and BF and their counterparts FFD and BFD are all asymptotically optimal in the sense that the ratio of expected wasted space to the expected occupied space E[σ(Ln)] = n/2 tends to 0 as . This is in sharp contrast to worst-case bounds, which show that, for infinitely many n > 0,

OCR for page 87

Probability and Algorithms
WH(Ln)/σ(Ln) can be as large as 7/10 for H = FF or BF and as large as 2/9 for H = FFD or BFD (Johnson et al., 1974).
The shortcomings of the Θ(·) results are apparent, because the average-case results do not distinguish between FFD, BFD, and OPT. On the other hand, the average-case results do show that for all n sufficiently large, E[FF(Ln)] > E[BF(Ln)]; a comparable distinction does not appear in the worst-case results.
7.1.4 Ms Algorithms
We describe three algorithms. The simplest is the on-line list scheduling (LS) algorithm, which schedules the tasks in the given sequence X1, ..., Xn on the processors P1, ..., Pm, with X1 starting on P1. LS schedules Xi, , on that processor having the smallest workload in the schedule for X1, ..., Xi-1, with ties broken in favor of lower-indexed processors. By the workload of a processor, we mean the total duration of the tasks already scheduled on that processor. As before, LS can be improved by first sorting Ln into decreasing order. LS along with the initial sorting is called the largest processing time (LPT) algorithm.
The third MS heuristic was originally proposed for a somewhat different optimization problem: With the instances (Ln, m) the same as in the MS problem, the objective of the set-partitioning (SP) problem is to find a schedule that minimizes the difference in the maximum and minimum processor workloads. Clearly, one expects a good heuristic for SP to be a good heuristic for MS; indeed, the two problems are obviously identical for m = 2. The heuristic described below is a set-differencing method (Karmarkar and Karp, 1982). It can be extended to all , but we confine ourselves to the case m = 2, because it is easier to describe and analyze.
Two tasks X and Y in list L are said to be differenced in L when a new list L' is formed from L by replacing X and Y with a task having duration |X-Y|. The largest-first differencing (LFD) heuristic applied to for m = 2 begins by differencing the largest two tasks in to form . Then the largest two tasks are differenced in to form . This procedure continues until a list of one task remains. LFD defines a schedule for Ln by requiring that the tasks differenced in , , be scheduled on different processors and by requiring that the final processor workloads differ by the duration of the task in . This schedule is easily developed by working backward through the sequence of

OCR for page 87

Probability and Algorithms
differencing operations. First, the task in is put on one or the other of the two processors. Suppose the schedule for , has been formed, and let X and Y be the tasks differenced in . Then the schedule for is formed from the schedule for by removing a task of duration |X-Y| and then scheduling X and Y on different processors so as to preserve the processor workload difference, i.e., the duration of the task in .
In analogy with (7.1), typical illustrations of probabilistic results can be found in the analysis of the processor idle time averaged over the m processors,
We assume m = 2, so that AH(Ln, 2) is simply half the difference between the two processor finishing times in the schedule produced by H. A satisfactory analysis of LFD remains an open problem, but Karmarkar and Karp (1982) have studied a randomized, more easily analyzed modification of LFD that we denote LFD*. Results for LS, LPT, and LFD* with X ~ U(0, 1) are shown in Table 7.2. In the order given, the algorithms are increasingly more complicated and increasingly more difficult to analyze, but they yield schedules that are increasingly more efficient for large n.
7.2 Analytical Techniques
We describe and illustrate below a number of the more important techniques that have been successfully applied to the analysis of BP and MS problems. A more extensive discussion appears in Coffman et al. (1988).
7.2.1 Markov Chains
For the simpler BP and MS heuristics, it is sometimes possible to formulate a tractable Markov chain that represents the element-by-element development of partitions. A state of the Markov chain must represent block sums in a suitable way; given the state space, the transition function is defined by the heuristic. Results for general n are obtained by a transient analysis, whereas asymptotics for large n are obtained by a steady state analysis.
To illustrate ideas, consider the average-case analysis of LS on m = 2 processors, and assume that F(x) is the uniform distribution on [0, 1]. Define Vi as the (positive) difference between the processor finishing times after the

OCR for page 87

Probability and Algorithms
TABLE 7.2: Analysis of Makespan Scheduling Algorithms
List Scheduling:
E[ALS(Ln, 2)] = 1/6
Feller (1971)
Largest Processing Time:
Coffman et al. (1984a)
Modified Largest Difference First:
There exists a c > 0 such that, with a probability that tends to 1 as ,
ALFD*(Ln, 2) = O(n-clogn)
Karmarkar and Karp (1982)
first i tasks have been scheduled. The following recurrence is easily verified:
Since the Xi are i.i.d. random variables, is a Markov chain. A routine analysis shows that the density for Vi is given by fi(x) = 2(1-x), for all i > 2 (Feller, 1971). Then we obtain the result cited in °7.1, viz. E[ALS(Ln, 2)] = E[Vn]/2 = 1/6. Since and LS(L n, 2) = [Vn + σ(Ln)]/2, we also have the relative performance bound

OCR for page 87

Probability and Algorithms
As another example, is a bivariate Markov chain, where ln is the level, i.e., sum of item sizes, in the last bin of an NF packing of Ln. An analysis of this chain for X ~ U(0, 1) shows that , (Hofri, 1984), thus refining the asymptotic result cited in °7.1. Indeed, an explicit expression for the distribution of NF(Ln) has been derived in Hofri (1984).
Unfortunately, Markov chain approaches seem to be limited to the relatively simplistic, less-efficient heuristics; the state spaces of Markov chains for other heuristics like FF and BF simply become too large and unwieldy.
7.2.2 Bounds
The immediate advantage of bounds is that they lead to a tractable analysis. The obvious sacrifice is that they provide only partial information. However, this information is often sufficient to choose between alternative heuristics. For example, the results cited in °7.1 for FF, BF, FFD, and BFD were all obtained by bounding techniques, yet they show that for all n sufficiently large, we have E[FF(Ln)] > E[BF(Ln)] > E[H(Ln)], where H stands for either FFD or BFD. As illustrated below, bounding techniques have appeared in two basic forms.
Bounding the Objective Function. In analyzing the BP heuristic H, it may be possible to find a function g(Ln) such that for all Ln and such that E[g(Ln)] is easily calculated. Then we have the average-case bound . A similar approach applies to the analysis of MS heuristics.
As a concrete example, we consider the LPT heuristic and its average idle time, as defined by (7.2). We have (Loulou, 1984; Frenk and Rinnooy Kau, 1987)
To see the latter inequality, let i be the largest index such that X(i) runs until the end of the schedule. Then just after X(i) is scheduled, the average processor idle time up to the end of the schedule is at most . Each task X(k) scheduled after X(i) reduces the average idle time by X(k)/m; (7.3) follows easily.

OCR for page 87

Probability and Algorithms
To illustrate the use of the bound (7.3), we show that (Frenk and Rinnooy Man, 1987)
when and F(x) is strictly increasing in (0, σ) for some σ > 0. Bounding the right-hand side of (7.3) by
we observe that the first term in (7.5) converges (a.s.) to as and that it can be made arbitrarily small by an appropriate choice of . Also, since , , (a.s.). Moreover, converges (a.s.) to a positive constant as for every . Thus, the second tern within the maximization in (7.5) tends to (a.s.). We conclude that (7.4) holds.
In some cases, the requirement that a bound hold deterministically for all Ln is too stringent to yield good results. In addition to a bound that always holds, there may exist a sharper bound g'(Ln) such that except on a set having a small probability qn. If sufficiently rapidly that , then we have
Dominating Algorithms. A common way to upper-bound H(Ln) is to introduce a simpler, more easily analyzed algorithm H' for which it can be proved that for all Ln. In this case, H' is said to dominate H. A similar approach applies to lower bounds. For example, the MATCH heuristic described below is dominated by both FFD and BFD.
The MATCH packing heuristic iterates the following procedure until all items are packed. Let S denote the set of items that remain to be packed. MATCH first finds a largest item in S, say X. If |S| = 1 or if no remaining item fits with X, i.e., Y + X > 1 for all , then MATCH puts X into a bin alone. Otherwise, MATCH puts items X and X' into a bin alone, where X' is a largest remaining item other than X such that .
It can be proved without much difficulty that and for all Ln (Lueker, 1982). Moreover, MATCH

OCR for page 87

Probability and Algorithms
has the following simple analysis when X ~ U(0, 1). First, we have that , where b is the number of singleton bins in the MATCH packing. The number of singletons with an item no larger than 1/2 is at most one, so , where b' is the number of singletons with an item larger than 1/2. But an inspection of MATCH shows that b' is equal in distribution to , where ξi is a symmetric, n-step random walk starting at the origin. Standard results then yield and hence , where H stands for either FFD or BFD.
7.2.3 Stochastic Planar Matching
Matching problems in one or more dimensions have arisen in the analysis of several packing heuristics. An example in one dimension was given in °7.2.2. Here, we first define a generalization of this matching problem to two dimensions and then illustrate how it occurs in the analysis of algorithms.
Let n plus points and n minus points be chosen independently and uniformly at random in the unit square. Let Mn denote a maximum up-right matching of plus points to minus points such that if a plus at (x, y) is matched to a minus at (x', y'), then and . Let Un denote the number of points left unmatched by Mn. The problem of determining the distribution of Un is called the up-right matching problem. Asymptotic bounds on the expected value are given by (Leighton and Shot, 1986; Rhee and Talagrand, 1988; Shor, 1986)
To illustrate the applications of (7.6), we consider the upper-bound analysis of the BF heuristic in Shor (1986), assuming that X ~ U(0, 1). Define the modified best fit (MBF) heuristic to be the same as BF except that MBF closes a bin to any further items whenever the bin receives an item no larger than 1/2. Clearly, bins in an MBF packing have at most two items. It is not difficult to prove that MBF dominates BF, so that .
Next, we describe MBF as a matching procedure. Plot the items of Ln as points in the left half of the unit square so that Xi has a y coordinate 1-i/n and an x coordinate Xi if , and 1-Xi if . Xi is plotted as a plus point if and as a minus point if . Now match a plus point with a minus point if the corresponding items are placed in the same bin by MBF. By definition of MBF, the minus point must be

OCR for page 87

Probability and Algorithms
above the plus point, because the item corresponding to the minus point had to be scanned first. Also, the minus point must be to the right of the plus point, because the two items fit into a single bin. An MBF matching is a maximum up-right matching, as is easily verified. However, the model differs from the original one in two respects. First, points are samples in the left half of the unit square, and second, the x coordinate has been discretized so that . But it is easy to prove that (7.6) still holds; the effects of both differences are limited to changes in the hidden multiplicative constant.
Finally, we observe that MBF(Ln) is the sum of the occupied space σ(Ln) and the unoccupied space, the latter quantity being bounded by Un. Thus, , and hence
7.2.4 Linear Programming
If the item sizes in Ln, make up a discrete set, then BP is easily formulated as an integer program. Let s1, ..., sN be the different item sizes in Ln and let mj, be the number of items with size sj. Define the ith possible configuration as a sequence of integers , , such that , i.e., a set of items with Cij of size sj, , can be packed into a single bin. If M denotes the number of possible configurations, then , where solves the integer program: minimize subject to , , and , .
Relaxations of such integer programs lead to useful bounds for the analysis of optimum solutions. For example, suppose we relax the integer program for Ln so that the ti can be arbitrary nonnegative reals. Then it is readily shown that
where LIN(Ln) denotes a solution to the relaxed problem.
To illustrate the bound, consider the packing constant
We win show that for general F(x), (Rhee and Talagrand, 1989b). This will also give us one of the many applications of Kolmogorov-Smirnov statistics to the analysis of BP and MS.

OCR for page 87

Probability and Algorithms
To begin, for some integer to be chosen later, transform the given distribution F to a distribution G consisting of N atoms, each of weight 1/N, at sj = F-1(j/N), . If cN denotes the packing constant under G, then it is not hard to see that . Note that generating n items Xi according to G can be achieved by taking n uniform samples Ui from [0,1] and setting Xi = F-1([NUi]/N),
To investigate cN, consider the one-sided Kolmogorov-Smirnov statistic , where
If we remove from Ln the items generated by the largest of the Ui and pack them one per bin, we are left with a list of items with sizes in such that
We have , where contains exactly [n/N] items of each size sj. Finally, let denote the solution value of the LP relaxation for in which we pack exactly n/N (rather than [n/N]) of each item size. By (7.7), we have , and by the law of large numbers, we have . Hence we obtain the bound
The standard bound, , along with the choice then yields , where the hidden constant is independent of the distribution.
Duality theory has played a role in studies of the perfect packing problem: For which distributions F do we have the packing constant c(F) = E[X], so that ? The dual of the integer program for BP is: Find a set of nonnegative weights uj such that mjuj is maximized subject to , . Note that the constraint simply requires that for any set of items fitting into a bin, the corresponding sum of weights must be at most 1.
The perfect packing problem was first studied within the class of uniform distributions U(a, b), . Motivated by the dual problem above, a weighting function approach was adopted in Lueker (1983). We

OCR for page 87

Probability and Algorithms
say that is a weighting function if for all finite sequences quences x1, ..., xk of positive reals, . It is easy to see that if u is a weighting function, then . Using this relation and a computer program to help in the search, Lueker (1983) found weighting functions classifying the distributions U(a, b) such that . For the general problem, Rhee and Talagrand (1989a, b) proved strong results drawing on ideas from functional analysis and topology. Courcoubetis and Weber (1986) studied the same problem within the class of on-line algorithms.
7.3 Related Topics
This section describes some of the more important questions that have grown out of the initial probabilistic studies of BP and MS.
7.3.1 Variants
The following problem has the same instance Ln as BP.
Bin Covering. Partition Ln into a maximum number of subsets (bins) such that each subset sums to at least 1.
The NF algorithm can be adapted to this problem in an obvious way. Applying standard results in renewal theory to the case X ~ U(0, 1), Csirik et al. (1991) analyzed this variant of NF bin packing to obtain precise estimates of the expected number of bins covered.
The next problem has the same instance (Ln, m) as MS.
Dual Bin Packing. Find a subset of maximum cardinality C(Ln, m) such that can be partitioned into m subsets with each subset summing to no more than 1.
Asymptotics for E[C(Ln, m)] have been studied in Bruno and Downey (1985).
7.3.2 Higher Dimensions
Extensions of BP to two and three dimensions have strong practical motivations, especially in stock-cutting applications. In the two-dimensional strip

OCR for page 87

Probability and Algorithms
packing problem, the rectangles of a list Ln = (R1, ... , Rn) are to be packed into a unit-width, semi-infinite strip; the heights and widths of all rectangles are at most 1. The packing is to have these properties: (1) the rectangles do not overlap each other or the edges of the strip, (2) rectangles are placed with their sides parallel to the edges of the strip (90º rotations are disallowed), and (3) the packing height is minimized, where the packing height is the maximum height reached by the tops of the rectangles in a vertically oriented strip.
In the variant, two-dimensional bin packing, horizontal boundaries are also placed at the integer heights of the vertical strip. Each rectangle must now be wholly contained within a unit square, or ''bin,'' between some pair of consecutive integer heights. The objective is now to minimize the number of bins used in the packing.
The probabilistic analysis of two-dimensional packing has recently been surveyed in Coffman and Shot (1990). In the most common probability model, all rectangle heights and widths are taken to be independent samples from U(0, 1). The heuristics studied have, for the most part, been straightforward extensions of one-dimensional algorithms. For example, any one-dimensional heuristic can be adapted to level packings of the strip, in which rectangles are placed along levels, or horizontal baselines. The first level is the bottom of the strip. Each higher level passes through the top of a highest rectangle in the preceding level. Thus, the space between adjacent levels corresponds to a one-dimensional bin. Shelf packings (Bartholdi et al., 1989) are similar except that levels are preset at heights determined by the distribution of rectangle heights, which is assumed to be given in advance. In general, the probabilistic analysis of level and shelf algorithms extends in natural ways the analysis of one-dimensional bin packing.
The two-dimensional bin packing algorithm in Karp et al. (1984) is a less obvious generalization of one-dimensional matching; its analysis reduces to that of up-right matching.
7.3.3 General Bounds
Lower bounds for BP have been useful in estimating the cost of certain restrictions to the design of algorithms. For example, assume X ~ U(0, 1). Shor (1986) proved, as a result in stochastic planar matching, that

OCR for page 87

Probability and Algorithms
for any on-line algorithm. (More recently, Shor (1991) devised an on-line algorithm that achieves this lower bound without knowing n in advance.) It is interesting to note, however, that if we augment the class of on-line algorithms by those that can make use of the number n of items to be packed, then this bound no longer applies; Shor (1986) devised an algorithm of this type that wastes space on average.
In another example, again under U(0, 1), algorithms have been classified by the number of active bins needed during the packing process. Here, an active bin is simply a nonempty bin that has yet to be closed to further items. It has been shown (Coffman and Shor, 1992) that if an algorithm H never has more than r bins active at any time, then . Note that r = 1 for NF. This result also applies to all other on-line, linear-time algorithms studied in the literature (e.g., Ramanan and Tsuga, 1992; Lee and Lee, 1987); i.e., all of these algorithms limit the number of active bins and produce a wasted space whose expected value grows linearly in n.
7.3.4 Distributions
In studies of BP the emphasis has been on the uniform distribution U(0, 1), because it leads to a tractable analysis. Models of MS have concentrated on U(0, 1) and exponential distributions, for the same reason. However, there have been many useful results dealing with more general distributions, as illustrated in §§7.2.2 and 7.2.4. For example, the lower bound on E[OPT(Ln)] under U(0, 1) is easily shown to apply to any symmetric distribution on [0,1]. These results have also been proved for distributions with decreasing densities, by a technique of decomposing such distributions into a series of symmetric distributions.
In addition to the perfect packing results alluded to in §7.2.4, there have been several cases where the uniform distributions U(0, b) have been successfully handled. Among these are Karmarkar's (1982) analysis of NF and the analysis by Bentley et al. (1984) of FFD. The analysis has often led to anomalous and unexpected results. For example, the analysis of FFD revealed discontinuities at b = 1/2 and b = 1, as shown by the fact that E[WFFD(Ln)] is O(1) if , Θ(n1/3 ) if 1/2 < b < 1, and as noted earlier, if b=1.
Quite recently, discrete uniform distributions have been studied in depth (Coffman et al., 1991). The results have shown that many aspects of average-case behavior are lost in the passage to continuous approximations U(a,b). To illustrate, let U{j,k} denote the uniform distribution on the set

OCR for page 87

Probability and Algorithms
, . Results for the continuous case do not suggest the following strong result: For any U{j, k} with , there is an on-line algorithm A such that E[A(Ln)-σ(Ln)] = O(1). The behavior of classical packing rules has also been shown to be much more irregular in the discrete cases. For example, expected wasted space O(1) and Θ(n) both occur under FFD for specific pairs j,k with j/k < 1/2 and with j/k > 1/2. As another example, there appear to be j, k such that FF produces O(1) expected wasted space, whereas FFD produces Θ(n) expected wasted space.
7.4 Directions for Further Study
There are obvious open problems concerned with more general distributions F(x) and more precise results, e.g., useful bounds on the multiplicative constants hidden in the asymptotic notation. Here, we note a few gaps in the asymptotic theory that have yet to be resolved, even under the usual simplifying assumptions. We begin with two conjectures.
Conjecture 1 For X ~ U(0, b), 0<b<1, we have E[WH(Ln)] = Θ(n) for H = FF or BF.
A similar conjecture applies to discrete distributions U{j,k} for .
The next conjecture refers to the expected processor idle time defined in (7.2). We again assume X ~ U (0, 1).
Conjecture 2 There exists an α > 0 such that E[AOPT(Ln, 2)] = O(eαn).
Strong results on the median of the distribution of AOPT(Ln, 2) are proved in Karmarkar et al. (1986). The analysis applies the second moment method (Erdös and Spencer, 1974).
The conjectures for one-dimensional packing have their counterparts in higher dimensions. An interesting open problem in two dimensions is the average-case behavior of the FF and BF rules applied to the level algorithms of strip packing.
Industrial applications of three-dimensional packing abound, yet the design and probabilistic analysis of algorithms remain at an early stage (see Karp et al., 1984; Li and Cheng, 1990). For example, the existence of on-line algorithms with sublinear expected wasted space remains an open question.

OCR for page 87

Probability and Algorithms
References
Bartholdi, J.J., J.H. Vande Vate, and J. Zhang (1989), Expected performance of the shelf heuristic for two-dimensional packing, Oper. Res. Lett. 8, 11-16.
Bentley, J.L., D.S. Johnson, F.T. Leighton, C.C. McGeoch, and L.A. McGeoch (1984), Some unexpected expected behavior results for bin packing, in Proc. 16th Annual ACM Symposium on Theory of Computing , ACM Press, New York, 279-288.
Bruno, J.L., and P.J. Downey (1985), Probabilistic bounds for dual bin packing, Acta Inf. 22, 333-345.
Coffman, E.G., Jr., and P.W. Shot (1990), Average-case analysis of cutting and packing in two dimensions, Eur. J. Oper. Res. 44, 134-144.
Coffman, E.G., Jr., and P.W. Shor (1992), Packing in two dimensions: Asymptotic average-case analysis of algorithms, Algorithmica, to appear.
Coffman, E.G., Jr., C.A. Courcoubetis, M.R. Garey, D.S. Johnson, L.A. McGeoch, P.W. Shot, R.R. Weber, and M. Yannakakis (1991), Average-case performance of bin packing algorithms under discrete uniform distributions, in Proc. 23rd A CM Symposium on the Theory of Computing, ACM Press, New York, 230-241.
Coffman, E.G., Jr., G.N. Frederickson, and G.S. Lueker (1984a), Expected makespans for largest-first scheduling of independent tasks on two processors, Math. Oper. Res. 9, 260-266.
Coffman, E.G., Jr., M.R. Garey, and D.S. Johnson (1984b), Approximation algorithms for bin packing—An up-dated survey, in Algorithm Design for Computer System Design, G. Ausiello, M. Lucertini, and P. Serafini, eds., Springer-Verlag, New York, 49-106.
Coffman, E.G., Jr., G.S. Lueker, and A.H.G. Rinnooy Kan (1988), Asymptotic methods in the probabilistic analysis of sequencing and packing heuris-

OCR for page 87

Probability and Algorithms
tics, Manage. Sci. 34, 266-290.
Coffman, E.G., Jr., K. So, M. Hofri, and A.C. Yao (1980), A stochastic model of bin packing, Inform. Contr. 44, 105-115.
Courcoubetis, C.A., and R.R. Weber (1986), Necessary and sufficient conditions for the stability of a bin packing system, J. Appl. Probab . 23, 989-999.
Csirik, J., J.B.G. Frenk, A. Frieze, G. Galambos, and A.H.G. Rinnooy Kan (1986), A probabilistic analysis of the next fit decreasing bin packing heuristic, Oper. Res. Lett. 5, 233-236.
Csirik, J., J.B.G. Frenk, G. Galambos, and A.H.G. Rinnooy Kan (1991), Probabilistic analysis of algorithms for dual bin packing problems, J. Algorithms 12, 189-203.
Dyckhoff, H. (1990), A typology of cutting and packing problems, Eur. J. Oper. Res. 44, 145-159.
Erdös, P., and J. Spencer (1974), Probabilistic Methods in Combinatorics , Academic Press, New York.
Feller, William (1971), An Introduction to Probability Theory and Its Applications, vol. II, John Wiley & Sons, New York, second edition.
Frenk, J.B.G., and A.H.G. Rinnooy Kan (1987), The asymptotic optimality of the LPT rule, Math. Oper. Res. 12, 241-254.
Garey, M.R., and D.S. Johnson (1983), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, New York.
Hofri, M. (1984), A probabilistic analysis of the next fit bin packing algorithm, J. Algorithms 5, 547-556.
Hofri, M., and S. Kamhi (1986), A stochastic analysis of the NFD bin packing algorithm, J. Algorithms 7, 489-509.
Johnson, D.S., A. Demers, J.D. Ullman, M.R. Garey, and R.L. Graham (1974), Worst-case performance bounds for simple one-dimensional packing

OCR for page 87

Probability and Algorithms
algorithms, SIAM J. Comput. 3, 299-325.
Karmarkar, N. (1982), Probabilistic analysis of some bin-packing algorithms, in Proc. 23rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, Calif., 107-111.
Karmarkar, N., and R.M. Karp (1982), The differencing method of set partitioning, Technical Report UCB/CSD 82/113, Computer Science Division (EECS), University of California at Berkeley, December.
Karmarkar, N., R.M. Karp, G.S. Lueker, and A.M. Odlyzko (1986), Probabilistic analysis of optimum partitioning, J. Appl. Probab. 23, 626-645.
Karp, R.M., M. Luby, and A. Marchetti-Spaccamela (1984), A probabilistic analysis of multidimensional bin packing problems, in Proc. 16th Annual A CM Symposium on Theory of Computing, ACM Press, New York, 289-298.
Lee, C.C., and D.T. Lee (1987), Robust on-line bin packing algorithms, Technical Report, Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, Ill.
Leighton, F.T., and P.W. Shor (1986), Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, in Proc. 18th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 91-103.
Li, K., and K.-H. Cheng (1990), On three-dimensional packing, SIAM J. Comput. 19, 847-865.
Loulou, R. (1984), Tight bounds and probabilistic analysis of two heuristics for parallel processor scheduling, Math. Oper. Res. 9, 142-150.
Lueker, G.S. (1982), An average-case analysis of bin packing with uniformly distributed item sizes, Technical Report 181, Department of Information and Computer Science, University of California at Irvine.
Lueker, G.S. (1983), Bin packing with items uniformly distributed over intervals [a, b], in Proc. 24th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, Calif., 289-297.

OCR for page 87

Probability and Algorithms
Ramanan, P., and K. Tsuga (1992), Average-case analysis of the modified harmonic algorithm, Algorithmica, to appear.
Rhee, W.T., and M. Talagrand (1988), Exact bounds for the stochastic upward matching problem, Trans. Amer. Math. Soc. 307, 109-125.
Rhee, W.T., and M. Talagrand (1989a), Optimal bin packing with items of random sizes—II, SIAM J. Comput. 18, 139-151.
Rhee, W.T., and M. Talagrand (1989b), Optimal bin packing with items of random sizes—III, SIAM J. Comput. 18, 473-486.
Shor, P.W. (1986), The average-case analysis of some on-line algorithms for bin packing, Combinatorica 6, 179-200.
Shor, P.W. (1991), How to do better than best-fit: Tight bounds for average-case on-line bin packing, in Proc. 32nd Annual Symposium on Foundations of Computer Science, IEEE Computer Science Press, Los Alamitos, Calif., 752-759.

OCR for page 87

Probability and Algorithms
This page in the original is blank.