Вероятностный анализ одного алгоритма упаковки прямоугольников в полосу
Аннотация
Список литературы
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.
Рецензия
Для цитирования:
Кузюрин Н.Н., Поспелов А.И. Вероятностный анализ одного алгоритма упаковки прямоугольников в полосу. Труды Института системного программирования РАН. 2010;19.
For citation:
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.)