Probabilistic analysis a algorithm for strip packing
Abstract
In the article an on-line algorithm for packing rectangles into a strip is presented and studied. The estimation of expected wasted ratio for the algorithm is obtained.
About the Authors
N. N. Kuzjurin
ISP RAS, Moscow
Russian Federation
Russian Federation
A. I. Pospelov
ISP RAS, Moscow
Russian Federation
Russian Federation
References
1. B.S. Baker, E.J. Coffman and R.L. Rivest, Orthogonal packings in two dimensions, SIAM J. Computing, (1980) 9, 846--855.
2. B.S. Baker, J.S. Schwartz, Shelf algorithms for two dimensional packing problems. SIAM J. Computing, (1983) 12, 508--525
3. E.G. Coffman, Jr., C. Courcoubetis, M.R. Garey, D.S. Johnson, P.W. Shor, R.R. Weber, M. Yannakakis, Perfect packing theorems and the average-case bahavior of optimal and online bin packing, SIAM Review, (2002) 44 (1), 95--108.
4. R.M. Karp, M. Luby, A. Marchetti-Spaccamela, A probabilistic analysis of multidimensional bin packing problems, In: Proc. Annu. ACM Symp. on Theorty of Computing, 1984, pp. 289--298.
5. P. W. Shor, The average-case analysis of some on-line algorithms for bin packing. Combinatorica (1986) 6, 179-200.
6. P. W. Shor, How to pack better than Best Fit: Tight bounds for average-case on-line bin packing, Proc. 32nd Annual Symposium on Foundations of Computer Science, (1991) pp. 752-759.
7. E. G. Coffman, Jr., D. S. Johnson, P. W. Shor and G. S. Lueker. Probabilistic analysis of packing and related partitioning problems, Statistical Science (1993) 8, 40-47.
8. E. G. Coffman, Jr., P. W. Shor. Packings in two dimensions: Asymptotic average-case analysis of algorithms, Algorithmica (1993) 9, 253-277.
9. J. Csirik, G.J. Woeginger, Shelf Algorithms for On-Line Strip Packing. Inf. Process. Lett. (1997), 63(4), 171-175.
10. Кузюрин Н.Н., Поспелов А.И., Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу, Дискретная математика, 2006, т. 18, N 1, с. 76--90.
11. C. Kenyon and E. Remila, A near optimal solution to a two-dimensional cutting stock problem, Mathematics of Operations Research, (2000) 25, 645--656.
12. R. Motwani and P. Raghavan, Randomized algorithms, Cambridge Univ. Press, 1995.
13. W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Sattist. Assoc., 1963, v. 58, N 301, pp. 13--30.
14. E.J. Coffman, M.R. Garey, D.S. Johnson and R.E. Tarjan, Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. Computing, (1980) 9, 808--826.
Review
For citations:
Kuzjurin N.N., Pospelov A.I. Probabilistic analysis a algorithm for strip packing. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2010;19. (In Russ.)
Email this article 