SpringerLink
Log in

Online Bin Packing of Squares and Cubes

  • Conference paper
  • First Online:
Algorithms and Data Structures (WADS 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12808))

Included in the following conference series:

  • 1080 Accesses

Abstract

In the d-dimensional online bin packing problem, hyper-cubes of positive sizes no larger than 1 are presented one by one to be assigned to positions in d-dimensional unit cube bins. In this work, we provide improved upper bounds on the asymptotic competitive ratio for square and cube bin packing problems, where our bounds do not exceed 2.0885 and 2.5735 for square and cube packing, respectively. To achieve these results, we adapt and improve a previously designed harmonic-type algorithm, and apply a different method for defining weight functions. We detect deficiencies in the state-of-the-art results by providing counter-examples to the current best algorithms and the analysis, where the claimed bounds were 2.1187 for square packing and 2.6161 for cube packing.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.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

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 85.59
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 106.99
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Azar, Y., Cohen, I.R., Kamara, S., Shepherd, F.B.: Tight bounds for online vector bin packing. In: Proceedings of the 45th ACM Symposium on Theory of Computing (STOC 2013), pp. 961–970 (2013)

    Google Scholar 

  2. Balogh, J., Békési, J., Dósa, G., Epstein, L., Levin, A.: A new and improved algorithm for online bin packing. In: Proceedings of the 26th European Symposium on Algorithms (ESA 2018), pp. 5:1–5:14 (2018)

    Google Scholar 

  3. Balogh, J., Békési, J., Dósa, G., Epstein, L., Levin, A.: Lower bounds for several online variants of bin packing. Theory Comput. Syst. 63(8), 1757–1780 (2019). https://doi.org/10.1007/s00224-019-09915-1

    Article  MathSciNet  MATH  Google Scholar 

  4. Balogh, J., Békési, J., Dósa, G., Epstein, L., Levin, A.: A new lower bound for classic online bin packing. CoRR, abs/1807.05554 (2018). Also in Proceedings of the WAOA 2019

    Google Scholar 

  5. Balogh, J., Békési, J., Galambos, G.: New lower bounds for certain classes of bin packing algorithms. Theory Comput. Sys. 440–441, 1–13 (2012)

    MathSciNet  MATH  Google Scholar 

  6. Bansal, N., Correa, J.R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: inapproximability results and approximation schemes. Math. Oper. Res. 31(1), 31–49 (2006)

    Article  MathSciNet  Google Scholar 

  7. Blitz, D., Heydrich, S., van Stee, R., van Vliet, A., Woeginger, G.J.: Improved lower bounds for online hypercube and rectangle packing. CoRR, abs/1607.01229v2 (2016)

    Google Scholar 

  8. Brown, D.J.: A lower bound for on-line one-dimensional bin packing algorithms. Coordinated Science Laboratory report no. R-864 (UILU-ENG 78–2257) (1979)

    Google Scholar 

  9. Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Multidimensional bin packing and other related problems: a survey. Comput. Sci. Rev. 24, 63–79 (2017)

    Article  MathSciNet  Google Scholar 

  10. Coffman Jr., E.G., Garey, M., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 46–93. PWS Publishing Co., Boston (1996)

    Google Scholar 

  11. Coppersmith, D., Raghavan, P.: Multidimensional online bin packing: algorithms and worst case analysis. Oper. Res. Lett. 8, 17–20 (1989)

    Article  MathSciNet  Google Scholar 

  12. Csirik, J., Frenk, J.B.G., Labbe, M.: Two-dimensional rectangle packing: on-line methods and results. Discrete Appl. Math. 45(3), 197–204 (1993)

    Article  MathSciNet  Google Scholar 

  13. Csirik, J., van Vliet, A.: An on-line algorithm for multidimensional bin packing. Oper. Res. Lett. 13(3), 149–158 (1993)

    Article  MathSciNet  Google Scholar 

  14. Epstein, L.: Two-dimensional online bin packing with rotation. Theor. Comput. Sci. 411(31–33), 2899–2911 (2010)

    Article  MathSciNet  Google Scholar 

  15. Epstein, L.: A lower bound for online rectangle packing. J. Comb. Optim. 38(3), 846–866 (2019). https://doi.org/10.1007/s10878-019-00423-z

    Article  MathSciNet  MATH  Google Scholar 

  16. Epstein, L., Mualem, L.: Online bin packing of squares and cubes. CoRR, abs/2105.08763 (2021)

    Google Scholar 

  17. Epstein, L., van Stee, R.: Online square and cube packing. Acta Informatica 41(9), 595–606 (2005). https://doi.org/10.1007/s00236-005-0169-z

    Article  MathSciNet  MATH  Google Scholar 

  18. Epstein, L., van Stee, R.: Optimal online algorithms for multidimensional packing problems. SIAM J. Comput. 35(2), 431–448 (2005)

    Article  MathSciNet  Google Scholar 

  19. Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within \(1+\varepsilon \) in linear time. Combinatorica 1(4), 349–355 (1981). https://doi.org/10.1007/BF02579456

    Article  MathSciNet  MATH  Google Scholar 

  20. Fujita, S., Hada, T.: Two-dimensional on-line bin packing problem with rotatable items. Theor. Comput. Sci. 289(2), 939–952 (2002)

    Article  MathSciNet  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  22. Galambos, G., van Vliet, A.: Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms. Computing 52(3), 281–297 (1994). https://doi.org/10.1007/BF02246509

    Article  MathSciNet  MATH  Google Scholar 

  23. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of of NP-Completeness. Freeman and Company, San Francisco (1979)

    MATH  Google Scholar 

  24. Han, X., Chin, F.Y., Ting, H.-F., Zhang, G., Zhang, Y.: A new upper bound 2.5545 on 2D online bin packing. ACM Trans. Algorithms 7(4) (2011). Article 50

    Google Scholar 

  25. Han, X., Ye, D., Zhou, Y.: Improved online hypercube packing. CoRR, abs/cs/0607045 (2016). Also in Proceedings of the WAOA 2006

    Google Scholar 

  26. Han, X., Ye, D., Zhou, Y.: A note on online hypercube packing. CEJOR 18(2), 221–239 (2010). https://doi.org/10.1007/s10100-009-0109-z

    Article  MathSciNet  MATH  Google Scholar 

  27. Heydrich, S., van Stee, R.: Beating the harmonic lower bound for online bin packing. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp. 41:1–41:14 (2016)

    Google Scholar 

  28. Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8(3), 272–314 (1974)

    Article  MathSciNet  Google Scholar 

  29. Johnson, D.S., Demers, A., Ullman, J., Garey, M., Graham, R.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299–325 (1974)

    Article  MathSciNet  Google Scholar 

  30. Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982), pp. 312–320 (1982)

    Google Scholar 

  31. Liang, F.M.: A lower bound for on-line bin packing. Inf. Process. Lett. 10(2), 76–79 (1980)

    Article  MathSciNet  Google Scholar 

  32. Lee, C.C., Lee, D.T.: A simple online bin packing algorithm. J. ACM 32(3), 562–572 (1985)

    Article  Google Scholar 

  33. Miyazawa, F.K., Wakabayashi, Y.: Cube packing. Theor. Comput. Sci. 297(1–3), 355–366 (2003)

    Article  MathSciNet  Google Scholar 

  34. Ramanan, P., Brown, D.J., Lee, C.C., Lee, D.T.: On-line bin packing in linear time. J. Algorithms 10(3), 305–326 (1989)

    Article  MathSciNet  Google Scholar 

  35. Rothvoss, T.: Better bin packing approximations via discrepancy theory. SIAM J. Comput. 45(3), 930–946 (2016)

    Article  MathSciNet  Google Scholar 

  36. Seiden, S.S.: On the online bin packing problem. J. ACM 49(5), 640–671 (2002)

    Article  MathSciNet  Google Scholar 

  37. Seiden, S.S., van Stee, R.: New bounds for multidimensional packing. Algorithmica 36(3), 261–293 (2003). https://doi.org/10.1007/s00453-003-1016-7

    Article  MathSciNet  MATH  Google Scholar 

  38. Ullman, J.D.: The performance of a memory allocation algorithm. Technical report 100, Princeton University, Princeton, NJ (1971)

    Google Scholar 

  39. van Vliet, A.: An improved lower bound for online bin packing algorithms. Inf. Process. Lett. 43(5), 227–284 (1992)

    MATH  Google Scholar 

  40. van Vliet, A.: Lower and upper bounds for online bin packing and scheduling heuristics. Ph.D. thesis, Erasmus University, Rotterdam, The Netherlands (1995)

    Google Scholar 

  41. Yao, A.C.C.: New algorithms for bin packing. J. ACM 27(2), 207–227 (1980)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Haifa, Haifa, Israel

    Leah Epstein

  2. Department of Computer science, University of Haifa, Haifa, Israel

    Loay Mualem

Authors
  1. Leah Epstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Loay Mualem
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of Waterloo, Waterloo, ON, Canada

    Anna Lubiw

  2. University of Alberta, Edmonton, AB, Canada

    Mohammad Salavatipour

  3. Dalhousie University, Halifax, Canada

    Meng He

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Epstein, L., Mualem, L. (2021). Online Bin Packing of Squares and Cubes. In: Lubiw, A., Salavatipour, M., He, M. (eds) Algorithms and Data Structures. WADS 2021. Lecture Notes in Computer Science(), vol 12808. Springer, Cham. https://doi.org/10.1007/978-3-030-83508-8_26

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-83508-8_26

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-83507-1

  • Online ISBN: 978-3-030-83508-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation