Summary
Many problems, such as cutting stock problems and the scheduling of tasks with a shared resource, can be viewed as two-dimensional bin packing problems. Using the two-dimensional packing model of Baker, Coffman, and Rivest, a finite list L of rectangles is to be packed into a rectangular bin of finite width but infinite height, so as to minimize the total height used. An algorithm which packs the list in the order given without looking ahead or moving pieces already packed is called an on-line algorithm. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding approximation algorithms. Most of the approximation algorithms which have been studied are on-line except that they require the list to have been previously sorted by height or width. This paper examines lower bounds for the worst-case performance of on-line algorithms for both non-preordered lists and for lists preordered by increasing or decreasing height or width.
Similar content being viewed by others
References
Baker, B.S., Brown, D.J., Katseff, H.P.: A 5/4 Algorithm for two-dimensional bin packing. J. Algorithms 2, 348–368 (1981)
Baker, B.S., Coffman, E.G. Jr., Rivest, R.L.: Orthogonal packings in two dimensions. SIAM J. Comput. 9, 4, 846–855 (1980)
Baker, B.S., Schwarz, J.S.: Shelf algorithms for two-dimensional packing problems. Proceedings of the 1979 Conference on Information Sciences and Systems, Baltimore (1979). Also SIAM J. Comput. (to be published)
Brown, D.J.: On-line one-dimensional bin packing algorithms. Technical report ACT-19, Coordinated Science Laboratory, University of Illinois (1979)
Coffman, E.G. Jr.: Personal communication (1978)
Coffman, E.G., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. Comput. 9, 4, 808–826 (1980)
Golan, I.: Orthogonal oriented algorithms for packing in two dimensions. Draft (1978)
Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 4, 299–326 (1974)
Liang, F.M.: A lower bound for on-line bin packing. Info Proc Lett. 10, 2, 76–79 (1980)
Sleator, D.D.K.D.B.: A 2.5 times optimal algorithm for packing in two dimensions. Info Proc. Lett. 10, 1, 37–40 (1980)
Storer, J.A. (personal communication)
Author information
Authors and Affiliations
Additional information
This author's work was supported by the Joint Services Electronics Program (U.S. Army, U.S. Navy and U.S. Air Force) under Contract DAAG-29-78-C-0016
Rights and permissions
About this article
Cite this article
Brown, D.J., Baker, B.S. & Katseff, H.P. Lower bounds for on-line two-dimensional packing algorithms. Acta Informatica 18, 207–225 (1982). https://doi.org/10.1007/BF00264439
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00264439