Skip to main content
Springer Nature Link
Log in

On-line bin packing — A restricted survey

  • Articles
  • Published:
Zeitschrift für Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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

    Google Scholar 

  2. Baker BS, Brown DJ, Katseff HP (1981) A 5/4 algorithm for two-dimensional bin packing. J Algorithms 2:348–368

    Google Scholar 

  3. Baker BS, Coffman EG Jr, Rivest RL (1980) Orthogonal packings in two dimensions. SIAM J Comput 9:846–855

    Google Scholar 

  4. Baker BS, Schwartz JS (1983) Shelf algorithms for two-dimensional packing problems. SIAM J Comput 12:508–525

    Google Scholar 

  5. Brown AR (1971) Optimum packing and depletion. American Elsevier, New York

    Google Scholar 

  6. 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

  7. Brown DJ, Baker BS, Katseff HP (1982) Lower bounds for two-dimensional packing algorithms. Acta Informatica 8:207–225

    Google Scholar 

  8. Chandra B (1992) Does randomization help in on-line bin packing? Information Processing Lett 43:15–19

    Google Scholar 

  9. Chung FRK, Garey MR, Johnson DS (1982) On packing two-dimensional bins. SIAM J Alg Disc Meth 3:66–76

    Google Scholar 

  10. 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

    Google Scholar 

  11. Coffman EG Jr, Lueker GS (1992) Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics. Springer New York

    Google Scholar 

  12. Coppersmith D, Raghavan P (1989) Multidimensional on-line bin packing: Algorithms and worst case analysis. Operations Research Lett 8:17–20

    Google Scholar 

  13. Csirik J (1989) An on-line algorithm for variable-sized bin packing. Acta Informatica 26: 697–709

    Google Scholar 

  14. Csirik J, Imreh B (1989) On the worst-case performance of the NkF bin packing heuristic. Acta Cybernetica 9:89–105

    Google Scholar 

  15. 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

  16. Csirik J, Totik V (1988) Online algorithms for a dual version of bin packing. Discrete Applied Mathematics 21:163–167

    Google Scholar 

  17. Csirik J, Van Vliet A (1993) An on-line algorithm for multidimensional bin packing. Operations Research Lett 13:149–158

    Google Scholar 

  18. Fisher DC (1988) Next fit packs a list and its reverse into the same number of bins. Operations Research Lett 7:291–293

    Google Scholar 

  19. Friesen DK, Langston MA (1986) Variable sized bin packing. SIAM J Computing 15:222–230

    Google Scholar 

  20. Galambos G (1986) Parametric lower bounds for on-line bin packing. SIAM J Alg Disc Meth 7:362–367

    Google Scholar 

  21. Galambos G (1988) Notes on lee's harmonic fit algorithm. Annales Univ Sci Budapest Sect Comput 9:121–126

    Google Scholar 

  22. Galambos G (1991) A 1.6 lower bound for the two-dimensional on-line rectangle bin packing. Acta Cybernetica 10:21–24

    Google Scholar 

  23. 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

    Google Scholar 

  24. Galambos G, Kellerer H, Woeginger GJ (1994) A lower bound for on-line vector packing algorithms. To appear in Acta Cybernetica

  25. 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

    Google Scholar 

  26. Galambos G, Van Vliet A (1994) Lower bounds for 1-, 2-, and 3-dimensional on-line bin packing algorithms. Computing 52:281–297

    Google Scholar 

  27. Galambos G, Woeginger GJ (1993) Repacking helps in bounded space on-line bin-packing. Computing 49:329–338

    Google Scholar 

  28. Garey MR, Graham RL, Johnson DS, Yao ACC (1976) Resource constrained scheduling as generalized bin packing. J Comb Th Ser A21:257–298

    Google Scholar 

  29. Garey MR, Johnson DS (1974) Bounds on multiprocessor scheduling with resource constraints. SIAM J Comput 4:187–200

    Google Scholar 

  30. Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-completeness. Freeman San Francisco

    Google Scholar 

  31. Golomb S (1963) On certain non-linear recurring sequences. Am Math Monthly 70:403–405

    Google Scholar 

  32. Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17: 263–269

    Google Scholar 

  33. Hofri M (1987) Probabilistic analysis of algorithms. Springer Verlag New York

    Google Scholar 

  34. Johnson J (1974) Fast algorithms for bin packing. J Comput System Sci 8:272–314

    Google Scholar 

  35. 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

    Google Scholar 

  36. Kinnersley NG, Langston MA (1988) Online variable-sized bin packing. Discrete Applied Mathematics 22:143–148

    Google Scholar 

  37. Kou LT, Markowsky G (1977) Multidimensional bin packing algorithms. IBM J Res & Dev 21:443–448

    Google Scholar 

  38. 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

    Google Scholar 

  39. Lee CC, Lee DT (1985) A simple on-line bin packing algorithm. J Assoc Comput Mach 32:562–572

    Google Scholar 

  40. Liang FM (1980) A lower bound for on-line bin packing. Information Processing Lett 10: 76–79

    Google Scholar 

  41. Mao W (1993) Tight worst-case performance bounds for Next-k-Fit bin packing. SIAM J Comput 22:46–56

    Google Scholar 

  42. Mao W (1993) Best-k-fit bin packing. Computing 50:265–270

    Google Scholar 

  43. Ramanan P, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithms 10:305–326

    Google Scholar 

  44. Richey MB (1991) Improved bounds for harmonic-based bin packing algorithms. Discrete Applied Mathematics 34, 203–227

    Google Scholar 

  45. Salzer HE (1947) The approximation of numbers as sums of reciprocals. Am Math Monthly 54:135–142

    Google Scholar 

  46. Sleator DDKDB (1976) A 2.5 times optimal algorithm for packing in two dimensions. Information Processing Lett 10:37–40

    Google Scholar 

  47. Sleator DDKDB, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Comm ACM 28:202–208

    Google Scholar 

  48. Van Vliet A (1992) An improved lower bound for on-line bin packing algorithms. Information Processing Lett 43:277–284

    Google Scholar 

  49. Van Vliet A (1992) On the asymptotic worst case behaviour of harmonic fit. Report 9263/A, Econometric Institute, Erasmus University Rotterdam

    Google Scholar 

  50. Woeginger GJ (1993) Improved space for bounded-space on-line bin packing. SIAM J Discr Math 6:575–581

    Google Scholar 

  51. Yao ACC (1980) New algorithms for bin packing. J Assoc Comput Math 27:207–227

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Mathematik B, TU Graz, Kopernikusgasse 24, 8010, Graz, Austria

    Gábor Galambos

  2. Institut für Theoretische Informatik, TU Graz, Klosterwiesgasse 32/II, 8010, Graz, Austria

    Gerhard J. Woeginger

Authors
  1. Gábor Galambos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gerhard J. Woeginger
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was partially supported by the Christian Doppier Laboratorium für Diskrete Optimierung.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01415672

Key Words

Search

Navigation