Preview

Труды Института системного программирования РАН

Расширенный поиск

Вероятностный анализ одного алгоритма упаковки прямоугольников в полосу

Аннотация

В статье предлагается и теоретически исследуется on-line алгоритм упаковки прямоугольников в полубесконечную полосу

Об авторах

Н. Н. Кузюрин
ИСП РАН
Россия


А. И. Поспелов
ИСП РАН
Россия


Список литературы

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.)



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)