Abstract
In the classical bin packing problem, one is asked to pack items of various sizes into the minimum number of equal-sized bins. In the on-line version of this problem, the packer is given the items one by one and must immediately and irrevocably assign every item to its bin, without knowing the future items. Beginning with the first results in the early 1970's, we survey — from the worst case point of view — the approximation results obtained for on-line bin packing, higher dimensional versions of the problem, lower bounds on worst case ratios and related results.
Similar content being viewed by others
References
Assmann SF, Johnson DS, Kleitman DJ, Leung JYT (1984) On a dual version of the one-dimensional bin packing problem. J Algorithms 5:502–525
Baker BS, Brown DJ, Katseff HP (1981) A 5/4 algorithm for two-dimensional bin packing. J Algorithms 2:348–368
Baker BS, Coffman EG Jr, Rivest RL (1980) Orthogonal packings in two dimensions. SIAM J Comput 9:846–855
Baker BS, Schwartz JS (1983) Shelf algorithms for two-dimensional packing problems. SIAM J Comput 12:508–525
Brown AR (1971) Optimum packing and depletion. American Elsevier, New York
Brown DJ (1979) A lower bound for on-line one-dimensional bin packing algorithms. Tech Rep R-864, Coordinated Sci Lab Univ of Illinois Urbana
Brown DJ, Baker BS, Katseff HP (1982) Lower bounds for two-dimensional packing algorithms. Acta Informatica 8:207–225
Chandra B (1992) Does randomization help in on-line bin packing? Information Processing Lett 43:15–19
Chung FRK, Garey MR, Johnson DS (1982) On packing two-dimensional bins. SIAM J Alg Disc Meth 3:66–76
Coffman EG Jr, Garey MR, Johnson DS (1984) Approximation algorithms for bin packing: An updated survey. In: Analysis and Design of Algorithms in Combinatorial Optimization, Ausiello and Lucertini (eds) Springer Verlag New York 49–106
Coffman EG Jr, Lueker GS (1992) Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics. Springer New York
Coppersmith D, Raghavan P (1989) Multidimensional on-line bin packing: Algorithms and worst case analysis. Operations Research Lett 8:17–20
Csirik J (1989) An on-line algorithm for variable-sized bin packing. Acta Informatica 26: 697–709
Csirik J, Imreh B (1989) On the worst-case performance of the NkF bin packing heuristic. Acta Cybernetica 9:89–105
Csirik J, Johnson DS (1991) Bounded space on-line bin packing: Best ist better than First. Proc 2nd Ann ACM-SIAM Symp on Discrete Algorithms 309–319
Csirik J, Totik V (1988) Online algorithms for a dual version of bin packing. Discrete Applied Mathematics 21:163–167
Csirik J, Van Vliet A (1993) An on-line algorithm for multidimensional bin packing. Operations Research Lett 13:149–158
Fisher DC (1988) Next fit packs a list and its reverse into the same number of bins. Operations Research Lett 7:291–293
Friesen DK, Langston MA (1986) Variable sized bin packing. SIAM J Computing 15:222–230
Galambos G (1986) Parametric lower bounds for on-line bin packing. SIAM J Alg Disc Meth 7:362–367
Galambos G (1988) Notes on lee's harmonic fit algorithm. Annales Univ Sci Budapest Sect Comput 9:121–126
Galambos G (1991) A 1.6 lower bound for the two-dimensional on-line rectangle bin packing. Acta Cybernetica 10:21–24
Galambos G, Frenk JBG (1993) A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case. Discrete Applied Mathematics 41:173–178
Galambos G, Kellerer H, Woeginger GJ (1994) A lower bound for on-line vector packing algorithms. To appear in Acta Cybernetica
Galambos G, Van Vliet A (1993) An improved lower bound for on-line algorithms for the 2-dimensional rectangle bin packing problem. Report 9323/A, Econometric Institute, Erasmus University Rotterdam
Galambos G, Van Vliet A (1994) Lower bounds for 1-, 2-, and 3-dimensional on-line bin packing algorithms. Computing 52:281–297
Galambos G, Woeginger GJ (1993) Repacking helps in bounded space on-line bin-packing. Computing 49:329–338
Garey MR, Graham RL, Johnson DS, Yao ACC (1976) Resource constrained scheduling as generalized bin packing. J Comb Th Ser A21:257–298
Garey MR, Johnson DS (1974) Bounds on multiprocessor scheduling with resource constraints. SIAM J Comput 4:187–200
Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-completeness. Freeman San Francisco
Golomb S (1963) On certain non-linear recurring sequences. Am Math Monthly 70:403–405
Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17: 263–269
Hofri M (1987) Probabilistic analysis of algorithms. Springer Verlag New York
Johnson J (1974) Fast algorithms for bin packing. J Comput System Sci 8:272–314
Johnson DS, Demers A, Ullman JD, Garey MR, Graham RL (1974) Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J Comput 3:256–278
Kinnersley NG, Langston MA (1988) Online variable-sized bin packing. Discrete Applied Mathematics 22:143–148
Kou LT, Markowsky G (1977) Multidimensional bin packing algorithms. IBM J Res & Dev 21:443–448
Krause KL, Shen YY, Schwetman HD (1975) Analysis of several task-scheduling algorithms for a model of multiprogramming computer systems. J Assoc Comput Mach 22:522–550
Lee CC, Lee DT (1985) A simple on-line bin packing algorithm. J Assoc Comput Mach 32:562–572
Liang FM (1980) A lower bound for on-line bin packing. Information Processing Lett 10: 76–79
Mao W (1993) Tight worst-case performance bounds for Next-k-Fit bin packing. SIAM J Comput 22:46–56
Mao W (1993) Best-k-fit bin packing. Computing 50:265–270
Ramanan P, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithms 10:305–326
Richey MB (1991) Improved bounds for harmonic-based bin packing algorithms. Discrete Applied Mathematics 34, 203–227
Salzer HE (1947) The approximation of numbers as sums of reciprocals. Am Math Monthly 54:135–142
Sleator DDKDB (1976) A 2.5 times optimal algorithm for packing in two dimensions. Information Processing Lett 10:37–40
Sleator DDKDB, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Comm ACM 28:202–208
Van Vliet A (1992) An improved lower bound for on-line bin packing algorithms. Information Processing Lett 43:277–284
Van Vliet A (1992) On the asymptotic worst case behaviour of harmonic fit. Report 9263/A, Econometric Institute, Erasmus University Rotterdam
Woeginger GJ (1993) Improved space for bounded-space on-line bin packing. SIAM J Discr Math 6:575–581
Yao ACC (1980) New algorithms for bin packing. J Assoc Comput Math 27:207–227
Author information
Authors and Affiliations
Additional information
This work was partially supported by the Christian Doppier Laboratorium für Diskrete Optimierung.
Rights and permissions
About this article
Cite this article
Galambos, G., Woeginger, G.J. On-line bin packing — A restricted survey. ZOR - Methods and Models of Operations Research 42, 25–45 (1995). https://doi.org/10.1007/BF01415672
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01415672