Preview

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

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

Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу

Полный текст:

Аннотация

Предложен новый онлайновый алгоритм упаковки прямоугольников в полосу, существенно превосходящий известный алгоритм Коффмана-Шора по качеству получаемой упаковки.

Об авторе

М. А. Трушников
ИСП РАН
Россия


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

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

Просмотров: 60


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


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