Preview

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

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

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

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

Аннотация

В 1993 году Коффман и Шор предложили онлайновый алгоритм упаковки прямоугольников в полосу с оценкой O(n^{2/3}) для математического ожидания незаполненной площади полосы в стандартной вероятностной модели. С тех пор вопрос о возможности улучшения этой оценки в классе онлайновых алгоритмов оставался открытым. В данной работе проанализирован принципиально новый онлайновый алгоритм упаковки, предложенный ранее автором. Для него доказана оценка O(n^{1/2} (\log n)^{3/2}) для математического ожидания незаполненной площади полосы

Об авторе

М. А. Трушников
ИСП РАН
Соединённые Штаты Америки


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

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. Shor P. W. The average-case analysis of some on-line algorithms for bin packing. Combinatorica. 1986. V. 6. 2. P. 179-200.

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

5. Кузюрин Н. Н., Поспелов А. И. Вероятностный анализ нового класса алгоритмов упаковки прямоугольников в полосу. ЖВМиМФ. 2011. Т. 51, N 10, с. 1931-1936.

6. Кузюрин Н. Н., Поспелов А. И. Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу. Дискретная математика. 2006. Т. 18. 1. С. 76-90.

7. Csirik J., Woegenger G.J. Shelf algorithm for on-line strip packing, Inf. Process. Letters, 1997, v. 63, N 4, P. 171-175.

8. Трушников М.А., Об одной задаче Коффмана-Шора, связанной с упаковкой прямоугольников в полосу, Труды ИСП РАН, 2012 г., т. 22, с. 456-462.


Для цитирования:


Трушников М.А. Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу. Труды Института системного программирования РАН. 2013;24.

For citation:


Trushnikov M.A. Probabilistic analysis of a new strip packing algorithm. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2013;24. (In Russ.)

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


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


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