Geodesic
On-line algorithms for packing rectangles into several strips
Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 117-131.

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

The problem of packing rectangles into several strips is considered. It is shown that for this problem there exist on-line algorithms with multiplicative error asymptotically close to $2e$, where $e$ is the base of the natural logarithm. It is proved that none of the on-line algorithms can have the asymptotic multiplicative error less than $e$. 
@article{DM_2007_19_4_a7,
     author = {S. N. Zhuk},
     title = {On-line algorithms for packing rectangles into several strips},
     journal = {Diskretnaya Matematika},
     pages = {117--131},
     publisher = {mathdoc},
     volume = {19},
     number = {4},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_4_a7/}
}
TY  - JOUR
AU  - S. N. Zhuk
TI  - On-line algorithms for packing rectangles into several strips
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 117
EP  - 131
VL  - 19
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_4_a7/
LA  - ru
ID  - DM_2007_19_4_a7
ER  - 
%0 Journal Article
%A S. N. Zhuk
%T On-line algorithms for packing rectangles into several strips
%J Diskretnaya Matematika
%D 2007
%P 117-131
%V 19
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_4_a7/
%G ru
%F DM_2007_19_4_a7
S. N. Zhuk. On-line algorithms for packing rectangles into several strips. Diskretnaya Matematika, Tome 19 (2007) no. 4, pp. 117-131. http://geodesic.mathdoc.fr/item/DM_2007_19_4_a7/

[1] Garey M. R., Johnson D. S., Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, 1979 | MR | Zbl

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

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

[4] 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

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

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

[7] Ee-Chien Chang, Weiguo Wang, Kankanhalli M. S., “Multidimensional on-line bin-packing: An algorithm and its average-case analysis”, Inform. Process. Lett., 48:3 (1993), 121–125 | DOI | MR | Zbl

[8] Van Vliet A., “An improved lower bound for on-line bin packing algorithms”, Inform. Process. Lett., 43:5 (1992), 277–284 | DOI | MR | Zbl

[9] Graham R. L., “Bounds for certain multiprocessing anomalies”, Bell System Tech. J., 45 (1966), 1563–1581

[10] Albers S., “Better bounds for online scheduling”, SIAM J. Comput., 29 (1998), 459–473 | DOI | MR | Zbl

[11] Bartal Y., Fiat A., Karloff H., Vohra R., “New algorithms for an ancient scheduling problem”, J. Comput. Syst. Sci., 51 (1995), 359–366 | DOI | MR

[12] Faigle U., Kern W., Turán G., “On the performance of on-line algorithms for partition problems”, Acta Cybern., 9 (1989), 107–119 | MR | Zbl

[13] Karger D. R., Phillips S. J., Torng E., “A better algorithm for an ancient scheduling problem”, J. Algorithms, 20 (1996), 400–430 | DOI | MR | Zbl

[14] Bartal Y., Karloff H., Rabani Y., “A better lower bound for on-line scheduling”, Inform. Process. Lett., 50:3 (1994), 113–116 | DOI | MR | Zbl

[15] Caramia M., Giordani S., Iovanella A., “Grid scheduling by on-line rectangle packing”, Networks, 44 (2004), 106–119 | DOI | MR | Zbl

[16] Zhuk S. N., “Priblizhennye algoritmy upakovki pryamougolnikov v neskolko polos”, Diskretnaya matematika, 18:1 (2006), 91–105 | MR | Zbl

[17] Zhuk S., Chernykh A., Avetisyan A., Gaissaryan S., Grushin D., Kuzjurin N., Pospelov A., Shokurov A., “Comparison of scheduling heuristics for grid resource broker”, Proc. 5th Mexican Intern. Conf. Computer Sci., IEEE Computer Society, Washington, DC, 2004, 388–392

[18] Pospelov A. I., “Analiz odnogo algoritma upakovki pryamougolnikov, svyazannogo s postroeniem raspisanii dlya klasterov”, Trudy In-ta sistemnogo programmirovaniya. Matematicheskie metody i algoritmy, 6 (2004), 7–12