Geodesic
Approximate algorithms for packing rectangles into several strips
Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 91-105.

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

We consider a problem to pack rectangles into several semi-infinite strips of certain widths. We suggest two simply realised online algorithms, that is, algorithms which pack rectangles just at the moments of their arrivals. It is shown that the accuracy of the former algorithm cannot be approximated by any absolute constant. The latter algorithm guarantees a constant multiplicative accuracy, and the obtained estimate of the multiplicative accuracy is unimprovable.The research was supported by the Russian Foundation for Basic Research, grant 05–01–00798. 
@article{DM_2006_18_1_a6,
     author = {S. N. Zhuk},
     title = {Approximate algorithms for packing rectangles into several strips},
     journal = {Diskretnaya Matematika},
     pages = {91--105},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_1_a6/}
}
TY  - JOUR
AU  - S. N. Zhuk
TI  - Approximate algorithms for packing rectangles into several strips
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 91
EP  - 105
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_1_a6/
LA  - ru
ID  - DM_2006_18_1_a6
ER  - 
%0 Journal Article
%A S. N. Zhuk
%T Approximate algorithms for packing rectangles into several strips
%J Diskretnaya Matematika
%D 2006
%P 91-105
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2006_18_1_a6/
%G ru
%F DM_2006_18_1_a6
S. N. Zhuk. Approximate algorithms for packing rectangles into several strips. Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 91-105. http://geodesic.mathdoc.fr/item/DM_2006_18_1_a6/

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

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

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

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

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

[6] Drozdowski M., “Scheduling multiprocessor tasks—an overview”, European J. Oper. Research, 94 (1996), 215–230 | DOI | Zbl

[7] Foster, Kesselman C., The Grid: Blueprint for a future computing infrastructure, Morgan Kaufmann, San Francisco, 1999

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