Geodesic
Probabilistic analysis of shelf algorithms for packing rectangles into a strip
Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 76-90.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we consider algorithms to pack rectangles into a strip. As the main result we present an algorithm that packs rectangles online and for which the ratio of expected wasted area to expected occupied area tends to zero as the number of rectangles increases.The research was supported by the Russian Foundation for Basic Research, grants 05–01–00798 and 04–01–00359. 
@article{DM_2006_18_1_a5,
     author = {N. N. Kuzyurin and A. I. Pospelov},
     title = {Probabilistic analysis of shelf algorithms for packing rectangles into a strip},
     journal = {Diskretnaya Matematika},
     pages = {76--90},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_1_a5/}
}
TY  - JOUR
AU  - N. N. Kuzyurin
AU  - A. I. Pospelov
TI  - Probabilistic analysis of shelf algorithms for packing rectangles into a strip
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 76
EP  - 90
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_1_a5/
LA  - ru
ID  - DM_2006_18_1_a5
ER  - 
%0 Journal Article
%A N. N. Kuzyurin
%A A. I. Pospelov
%T Probabilistic analysis of shelf algorithms for packing rectangles into a strip
%J Diskretnaya Matematika
%D 2006
%P 76-90
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2006_18_1_a5/
%G ru
%F DM_2006_18_1_a5
N. N. Kuzyurin; A. I. Pospelov. Probabilistic analysis of shelf algorithms for packing rectangles into a strip. Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 76-90. http://geodesic.mathdoc.fr/item/DM_2006_18_1_a5/

[1] Baker B. S., Brown D. J., Katseff H. P., “A 5/4 algorithm for two-dimensional packing”, J. Algorithms, 2 (1981), 348–368 | DOI | MR | Zbl

[2] Baker B. S., Coffman E. J., Rivest R. L., “Orthogonal packings in two dimensions”, SIAM J. Computing, 9 (1980), 846–855 | DOI | MR | Zbl

[3] Baker B. S., Schwartz J. S., “Shelf algorithms for two dimensional packing problems”, SIAM J. Computing, 12 (1983), 508–525 | DOI | MR | Zbl

[4] Brucker P., Scheduling algorithms, Springer, Berlin, 1998 | MR

[5] Coffman E. J., Garey M. R., Johnson D. S., Tarjan R. E., “Performance bounds for level-oriented two-dimensional packing algorithms”, SIAM J. Computing, 9 (1980), 808–826 | DOI | MR | Zbl

[6] Coffman E. G., Jr., Garey M. R., Johnson D. S., “Approximation algorithms for Bin-Packing—An updated survey”, Algorithm design for computer system design, Springer, Berlin, 1984, 49–106 | MR

[7] Coffman E. G., Jr., Courcoubetis C., Garey M. R., Johnson D. S., Shor P. W., Weber R. R., Yannakakis M., “Perfect packing theorems and the average-case behavior of optimal and online bin packing”, SIAM Review, 44 (2002), 95–108 | DOI | MR | Zbl

[8] Csirik J., Johnson D. S., Kenyon C., Orlin J. B., Shor P. W., Weber R. R., “On the Sum-of-Squares algorithm for Bin Packing”, Proc. Annual ACM Symp. Theory of Computing, 2000, 208–217 | MR

[9] Karp R. M., Luby M., Marchetti-Spaccamela A., “A probabilistic analysis of multidimensional bin packing problems”, Proc. Annual ACM Symp. Theory of Computing, 1984, 289–298

[10] Kenyon C., Remila E., Math. Operat. Research, 25 (2000), 645–656 | DOI | MR | Zbl

[11] Motwani R., Raghavan P., Randomized algorithms, Cambridge Univ. Press, Cambridge, 1995 | MR | Zbl

[12] Sleator D. D., “A 2.5-times optimal algorithm for bin packing in two dimensions”, Inf. Processing Lett., 10 (1980), 37–40 | DOI | MR | Zbl

[13] Korf R. E., “Optimal rectangle packing: initial results”, Proc. Intern. Conf. on Automated Planning and Scheduling, 2003, 287–295