Geodesic
Probabilistic analysis of a new class of strip packing algorithms
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 51 (2011) no. 10, pp. 1931-1936 
N. N. Kuzyurin; A. I. Pospelov. Probabilistic analysis of a new class of strip packing algorithms. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 51 (2011) no. 10, pp. 1931-1936. http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_10_a15/
@article{ZVMMF_2011_51_10_a15,
     author = {N. N. Kuzyurin and A. I. Pospelov},
     title = {Probabilistic analysis of a~new class of strip packing algorithms},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1931--1936},
     year = {2011},
     volume = {51},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_10_a15/}
}
TY  - JOUR
AU  - N. N. Kuzyurin
AU  - A. I. Pospelov
TI  - Probabilistic analysis of a new class of strip packing algorithms
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2011
SP  - 1931
EP  - 1936
VL  - 51
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_10_a15/
LA  - ru
ID  - ZVMMF_2011_51_10_a15
ER  - 
%0 Journal Article
%A N. N. Kuzyurin
%A A. I. Pospelov
%T Probabilistic analysis of a new class of strip packing algorithms
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2011
%P 1931-1936
%V 51
%N 10
%U http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_10_a15/
%G ru
%F ZVMMF_2011_51_10_a15

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

A new class of algorithms for online packing of rectangles into a strip is proposed and studied. It is proved that the expectation of the unfilled area for this class of algorithms is $O(N^{2/3})$ in the standard (for this type of problems) probabilistic model for $N$ random rectangles.

[1] Csirik J., Woeginger G. J., “Shelf algorithms for on-line strip packing”, Inf. Process. Letters, 63:4 (1997), 171–175 | DOI | MR

[2] Karp R. M., Luby M., Marchetti-Spaccamela A., “A probabilistic analysis of multidimensional bin packing problems”, Proc. Ann. ACM Symp. on Theory of Comput., ACM, New York, 1984, 289–298

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

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

[5] Kenyon C., Remila E., “A near optimal solution to a two-dimensional cutting stock problem”, Math. Operat. Res., 25:1 (2000), 645–656 | DOI | MR | Zbl

[6] Shor P. W., “The average-case analysis of some on-line algorithms for bin packing”, Combinatorica, 6:2 (1986), 179–200 | DOI | MR | Zbl

[7] Shor P. W., “How to pack better than Best Fit: Tight bounds for average-case on-line bin packing”, Proc. 32nd Ann. Symp. Foundations of Comput. Sci., San Juan–Puerto Rico, 1991, 752–759

[8] Coffman E. G.(jr.), Johnson D. S., Shor P. W., Lueker G. S., “Probabilistic analysis of packing and related partitioning problems”, Statist. Sci., 8:1 (1993), 40–47 | DOI | MR

[9] Coffman E. G.(jr.), Shor P. W., “Packings in two dimensions: Asymptotic average-case analysis of algorithms”, Algorithmica, 9:3 (1993), 253–277 | DOI | MR | Zbl

[10] Kuzyurin N. N., Pospelov A. I., “Veroyatnostnyi analiz shelfovykh algoritmov upakovki pryamougolnikov v polosu”, Diskretnaya matem., 18:1 (2006), 76–90 | MR | Zbl

[11] Asgeirsson E., Ayesta U., Coffman E. et al., “Closed on-line bin packing”, Acta Cybernetica, 15:3 (2002), 361–367 | MR | Zbl

[12] Loev M., Teoriya veroyatnostei, Izd-vo inostr. lit., M., 1962 | MR