|
 ABSTRACT
This paper gives probabilistic analyses of two kinds of multidimensional bin packing problems: vector packing and rectangle packing. In the vector packing problem each of the d dimensions can be interpreted as a resource. A given object i consumes aij units of the jth resource, and the objects packed in any given bin may not collectively consume more than one unit of any resource. Subject to this constraint, the objects are to be packed into a minimum number of bins. The rectangle packing problem is more geometric in character. The ith object is a d-dimensional box whose jth side is of length aij, and the goal is to pack the objects into a minimum number of cubical boxes of side 1. We study these problems on the assumption that the aij are drawn independently from the uniform distribution over [0,1]. We study a vector packing heuristic called VPACK that tries to place two objects in each bin and a rectangle packing heuristic called RPACK that tries to pack one object into each of the 2d corners of each bin. We show that each of these heuristics tends to produce packings in which very little of the capacity of the bins is wasted. In the case of rectangle packing, we show that the results can be extended to a wide class of distributions of the piece sizes.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
M. Ajtai, J. Komlos, G. Tusnady (1982). On optimal matchings. Manuscript.
|
 |
2
|
|
| |
3
|
G.N. Frederickson (1980). Probabilistic analysis for simple one and two-dimensional bin packing algorithms. Information Processing Letters 11, 156-161.
|
| |
4
|
M. Hall (1967). Combinatorial Theory. Blaisdell Publishing Co.
|
| |
5
|
M. Hofri (1980). Two-dimensional packing: expected performance of simple level algorithms. Information and Control 45, 1-17.
|
| |
6
|
|
| |
7
|
R. Loulou (1982). Probabilistic behavior of optimal bin packing solutions. Tech. Rep., Faculty of Management, McGill University, Montreal, Canada.
|
| |
8
|
G. S. Lueker (1983a). An average-case analysis of bin packing. Manuscript, Department of Information and Computer Science, University of California at Irvine.
|
| |
9
|
G.S. Lueker (1983b). Bin packing with items uniformly distributed over intervals {a,b}.
|
| |
10
|
A. Renyi (1970). Probability Theory. North Holland.
|
CITED BY 10
|
|
|
|
|
Andris Ambainis , Eric Bach , Ashwin Nayak , Ashvin Vishwanath , John Watrous, One-dimensional quantum walks, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.37-49, July 2001, Hersonissos, Greece
|
|
|
E. G. Coffman, Jr. , C. Courcoubetis , M. R. Garey , D. S. Johnson , L. A. McGeoch , P. W. Shor , R. R. Weber , M. Yannakakis, Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.230-240, May 05-08, 1991, New Orleans, Louisiana, United States
|
|
|
F T Leighton , P Shor, Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.91-103, May 28-30, 1986, Berkeley, California, United States
|
|
|
E G Coffman, Jr. , F T Leighton, A provably efficient algorithm for dynamic storage allocation, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.77-90, May 28-30, 1986, Berkeley, California, United States
|
|
|
|
|
|
|
|
|
Danny Z. Chen , Xiaobo Hu , Yingping Huang , Yifan Li , Jinhui Xu, Algorithms for congruent sphere packing and applications, Proceedings of the seventeenth annual symposium on Computational geometry, p.212-221, June 2001, Medford, Massachusetts, United States
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2