Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
7 Probabilistic Analysis of Packing and Related Partitioning Problems
7 Probabilistic Analysis of Packing and Related Partitioning Problems
Pages 87-108
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 87... ...
These problems are drawn from important applications throughout industry, often under the name of stock cutting. This chapter bmedy surveys many of the basic results, as well as the probabilistic methods used to obtain them.
|
From page 88... ...
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)
|
From page 89... ...
. Typically, exact analysis of probability models is quite difficult, especially for the more efficient algorithms, so asymptotic techniques have been used.
|
From page 90... ...
, improve on NF by checking all nonempty bins before starting a new bin; i.e., FF and BE pack an item Xi into an empty bin if and only if Xi does not fit into any nonempty bin. FF packs Xi, i>2, 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.
|
From page 91... ...
denotes the sum of the item sizes in Ln. Note that FF and BE and their counterparts FED and BED are all asymptotically optimal in the sense that the ratio of expected wasted space EtWH]
|
From page 92... ...
I`FD ~O ~O . A, (, defines a schedule for In by requiring that the tasks differenced in Lit, 0 |
From page 93... ...
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.
|
From page 94... ...
random variables, {ViJi>o is a Markov chain. A routine analysis shows that the density for Vi is given by fife)
|
From page 95... ...
Unfortunately, Markov chain approaches seem to be limited to the relatively simplistic, less-e~cient heuristics; the state spaces of Markov chains for other heuristics like FF and BE simply become too large and unwieldy. 7.2.2 Bouncis The immediate advantage of bounds is that they lead to a tractable analysis.
|
From page 96... ...
A similar approach applies to lower bounds. For example, the MATCH heuristic described below is dominated by both FED and BED.
|
From page 97... ...
Plot the items of L72 as points in the left half of the unit square so that Xi has a y coordinate ~-i/n and an x coordinate Xi if Xi < 1/2, and 1-Xi if I/2 < Xi < 1. Xi is plotted as a plus point if Xi < l/2 and as a minus point if 1/2 < Xi < 1.
|
From page 98... ...
If M denotes the number of possible configurations, then OPT = Emetic, where {t: ~ solves the integer program: minimize ti subject to ti > 0, l |
From page 99... ...
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)
|
From page 100... ...
found weighting functions classifying the distributions U(a,b) such that c(U(a, b)
|
From page 101... ...
In the variant, tw - 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.
|
From page 102... ...
This result also applies to all other on-line, lineartime 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(O, 1)
|
From page 103... ...
Industrial applications of three-dimensional packing abound, yet the design and probabilistic analysis of algorithms remain at an earn stare (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.
|
From page 104... ...
Yannakakis (1991) , Average-case performance of bin packing algorithms under discrete uniform distributions, in Proc.
|
From page 105... ...
Rinnooy Kan (1991) , Probabilistic analysis of algorithms for dual bin packing problems, ~1.
|
From page 106... ...
, in Proc. 24th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, Calif., 289-297.
|
From page 107... ...
32nd Annuat Symposium on Foundations of Computer Science, {EKE Computer Science Press, fos Alamitos, Calif., 752-759.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.