Document Open Access Logo

Harmonic Algorithms for Packing d-Dimensional Cuboids into Bins

Author Eklavya Sharma

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.32.pdf
  • Filesize: 0.85 MB
  • 22 pages

Document Identifiers

Author Details

Eklavya Sharma
  • Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India

Acknowledgements

I want to thank my advisor, Prof. Arindam Khan, for his valuable comments, and Arka Ray for helpful suggestions.

Cite AsGet BibTex

Eklavya Sharma. Harmonic Algorithms for Packing d-Dimensional Cuboids into Bins. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.32

Abstract

We explore approximation algorithms for the d-dimensional geometric bin packing problem (dBP). Caprara [Caprara, 2008] gave a harmonic-based algorithm for dBP having an asymptotic approximation ratio (AAR) of (T_∞)^{d-1} (where T_∞ ≈ 1.691). However, their algorithm doesn't allow items to be rotated. This is in contrast to some common applications of dBP, like packing boxes into shipping containers. We give approximation algorithms for dBP when items can be orthogonally rotated about all or a subset of axes. We first give a fast and simple harmonic-based algorithm having AAR T_∞^d. We next give a more sophisticated harmonic-based algorithm, which we call HGaP_k, having AAR (T_∞)^{d-1}(1+ε). This gives an AAR of roughly 2.860 + ε for 3BP with rotations, which improves upon the best-known AAR of 4.5. In addition, we study the multiple-choice bin packing problem that generalizes the rotational case. Here we are given n sets of d-dimensional cuboidal items and we have to choose exactly one item from each set and then pack the chosen items. Our algorithms also work for the multiple-choice bin packing problem. We also give fast and simple approximation algorithms for the multiple-choice versions of dD strip packing and dD geometric knapsack.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • Geometric bin packing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mauro Maria Baldi, Guido Perboli, and Roberto Tadei. The three-dimensional knapsack problem with balancing constraints. Applied Mathematics and Computation, 218(19):9802-9818, 2012. URL: https://doi.org/10.1016/j.amc.2012.03.052.
  2. János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A new and improved algorithm for online bin packing. In European Symposium on Algorithms (ESA), pages 5:1-5:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.5.
  3. Nikhil Bansal, Alberto Caprara, and Maxim Sviridenko. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM Journal on Computing, 39(4):1256-1278, 2010. URL: https://doi.org/10.1137/080736831.
  4. Nikhil Bansal, Xin Han, Kazuo Iwama, Maxim Sviridenko, and Guochuan Zhang. A harmonic algorithm for the 3d strip packing problem. SIAM Journal on Computing, 42(2):579-592, 2013. URL: https://doi.org/10.1137/070691607.
  5. Nikhil Bansal and Arindam Khan. Improved approximation algorithm for two-dimensional bin packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 13-25, 2014. URL: https://doi.org/10.1137/1.9781611973402.2.
  6. Nikhil Bansal and Maxim Sviridenko. New approximability and inapproximability results for 2-dimensional bin packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 196-203, 2004. Google Scholar
  7. Andreas Bortfeldt and Gerhard Wäscher. Constraints in container loading-a state-of-the-art review. European Journal of Operational Research, 229(1):1-20, 2013. URL: https://doi.org/10.1016/j.ejor.2012.12.006.
  8. Alberto Caprara. Packing d-dimensional bins in d stages. Mathematics of Operations Research, 33:203-215, February 2008. URL: https://doi.org/10.1287/moor.1070.0289.
  9. Edward G. Coffman, János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo. Bin packing approximation algorithms: survey and classification. In Handbook of combinatorial optimization, pages 455-531. Springer New York, 2013. Google Scholar
  10. Edward G. Coffman, Michael R. Garey, David S. Johnson, and Robert E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9:808-826, 1980. URL: https://doi.org/10.1137/0209062.
  11. János Csirik and André van Vliet. An on-line algorithm for multidimensional bin packing. Operations Research Letters, 13(3):149-158, 1993. URL: https://doi.org/10.1016/0167-6377(93)90004-Z.
  12. Leah Epstein and Rob van Stee. Optimal online algorithms for multidimensional packing problems. SIAM Journal on Computing, 35(2):431-448, 2005. URL: https://doi.org/10.1137/S0097539705446895.
  13. Leah Epstein and Rob van Stee. This side up! ACM Transactions on Algorithms (TALG), 2(2):228-243, 2006. URL: https://doi.org/10.1145/1150334.1150339.
  14. Sándor P. Fekete and Jörg Schepers. A general framework for bounds for higher-dimensional orthogonal packing problems. Mathematical Methods of Operations Research, 60(2):311-329, 2004. URL: https://doi.org/10.1007/s001860400376.
  15. Wenceslas Fernandez de la Vega and George S. Lueker. Bin packing can be solved within 1+ε in linear time. Combinatorica, 1(4):349-355, 1981. URL: https://doi.org/10.1007/BF02579456.
  16. Paul C. Gilmore and Ralph E. Gomory. A linear programming approach to the cutting-stock problem. Operations Research, 9(6):849-859, 1961. URL: https://doi.org/10.1287/opre.9.6.849.
  17. Xin Han, Francis YL Chin, Hing-Fung Ting, Guochuan Zhang, and Yong Zhang. A new upper bound 2.5545 on 2D online bin packing. ACM Transactions on Algorithms (TALG), 7(4):1-18, 2011. URL: https://doi.org/10.1145/2000807.2000818.
  18. Klaus Jansen. A (3/2+ε) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 224-235, 2012. URL: https://doi.org/10.1145/2312005.2312048.
  19. Klaus Jansen and Lars Prädel. New approximability results for two-dimensional bin packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 919-936, 2013. URL: https://doi.org/10.1007/s00453-014-9943-z.
  20. Klaus Jansen and Lars Prädel. A new asymptotic approximation algorithm for 3-dimensional strip packing. In SOFSEM, pages 327-338, 2014. URL: https://doi.org/10.1007/978-3-319-04298-5_29.
  21. Klaus Jansen and Rob van Stee. On strip packing with rotations. In Symposium on Theory of Computing (STOC), pages 755-761. ACM, 2005. URL: https://doi.org/10.1145/1060590.1060702.
  22. Claire Kenyon and Eric Rémila. Approximate strip packing. In Foundations of Computer Science (FOCS), pages 31-36, 1996. URL: https://doi.org/10.1109/SFCS.1996.548461.
  23. Eugene L Lawler. Fast approximation algorithms for knapsack problems. Mathematics of Operations Research, 4(4):339-356, 1979. URL: https://doi.org/10.1287/moor.4.4.339.
  24. C. C. Lee and D. T. Lee. A simple on-line bin-packing algorithm. Journal of the ACM, 32(3):562-572, July 1985. URL: https://doi.org/10.1145/3828.3833.
  25. Flavio Keidi Miyazawa and Yoshiko Wakabayashi. Three-dimensional packings with rotations. Computers & Operations Research, 36(10):2801-2815, 2009. URL: https://doi.org/10.1016/j.cor.2008.12.015.
  26. James Munkres. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1):32-38, 1957. Google Scholar
  27. Boaz Patt-Shamir and Dror Rawitz. Vector bin packing with multiple-choice. Discrete Applied Mathematics, 160(10-11):1591-1600, 2012. URL: https://doi.org/10.1016/j.dam.2012.02.020.
  28. Prakash Ramanan, Donna J Brown, Chung-Chieh Lee, and Der-Tsai Lee. On-line bin packing in linear time. Journal of Algorithms, 10(3):305-326, 1989. URL: https://doi.org/10.1016/0196-6774(89)90031-X.
  29. Steven S Seiden. On the online bin packing problem. Journal of the ACM, 49(5):640-671, 2002. URL: https://doi.org/10.1145/585265.585269.
  30. Eklavya Sharma. Harmonic algorithms for packing d-dimensional cuboids into bins. ArXiv, 2011.10963, 2020. URL: http://arxiv.org/abs/2011.10963.
  31. Y. G. Stoyan and Andrey M. Chugay. Packing different cuboids with rotations and spheres into a cuboid. Advances in Decision Sciences, 2014, 2014. URL: https://doi.org/10.1155/2014/571743.
  32. Hu Zhang and Klaus Jansen. Scheduling malleable tasks. In Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact