Вероятностный анализ нового алгоритма упаковки прямоугольников в полосу
Аннотация
В 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.)
Послать статью по эл. почте 