Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу
Аннотация
Список литературы
1. Baker B. S., Coffman E. J., Rivest R. L. Orthogonal packings in two dimensions. SIAM J. Computing. 1980. V. 9. 4. P. 846-855.
2. Baker B. S., Schwartz J. S. Shelf algorithms for two dimensional packing problems. SIAM J. Computing. 1983. V. 6. 2. P. 508-525.
3. Karp R. M., Luby M., Marchetti-Spaccamela A. A probabilistic analysis of multidimensional bin packing problems. Proc. Annu, ACM Symp. on Theory of Computing. New-York: ACM. 1984. P 289-298.
4. Shor P. W. The average-case analysis of some on-line algorithms for bin packing. Combinatorica. 1986. V. 6. 2. P. 179-200.
5. Csirik J., Woeginger G. J. Shelf algorithm for on-line strip packing, Inf. Process. Lett. 1997. V. 63. 4, P. 171-175.
6. Coffman E. G., Jr, Shor P. W. Packing in two dimensions: Asymptotic average-case analysis of algorithms. Algorithmica. 1993. V. 9. 3. P. 253-277.
7. Кузюрин Н. Н., Поспелов А. И. Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу. Дискретная математика. 2006. Т. 18. 1. С. 76-90.
8. X. Han, K. Iwama, D. Ye, G. Zhang. Strip Packing vs. Bin Packing. Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science. 2009. V. 4508/2007. P. 358-367.
9. Кузюрин Н. Н., Поспелов А. И. Вероятностный анализ нового класса алгоритмов упаковки прямоугольников в полосу. ЖВМиМФ. 2011. Т. 51, N 10, с. 1931-1936.
10. Seiden S. S., On the online bin packing problem. J. ACM 49. 2002. P. 640-671.
Рецензия
Для цитирования:
Трушников М.А. Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу. Труды Института системного программирования РАН. 2012;22.
For citation:
Trushnikov M.A. On one problem of Koffman-Shor connected to strip packing problem. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;22. (In Russ.)