Annals of Computer Science and Information Systems, Volume 18

DOI: http://dx.doi.org/10.15439/2019F88

Citation: Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 18, pages 171–175 (2019)

Full text

Abstract. In this paper, we present a 1-space bounded cube packing algorithm with asymptotic competitive ratio 10.872.

References

1. L. Epstein and R. van Stee. Optimal online algorithms for multidimensional packing problems. SIAM Journal on Computing, 35(2):431–448, 2005.
2. P. Grzegorek and J. Januszewski. A note on one-space bounded square packing. Information Processing Letters, 115(11):872–876, 2015.
3. P. Grzegorek, J. Januszewski. Drawer algorithms for 1-space bounded multidimensional hyperbox packing. Journal of Combinatorial Optimization, 37(3): 1011-1044, 2019.
4. J. Januszewski and Ł. Zielonka. Online packing of rectangular items into square bins. In R. Solis-Oba and R. Fleischer, editors, Approximation and Online Algorithms. WAOA 2017, volume 10787 of Lecture Notes in Computer Science, pages 147–163, Cham, 2018. Springer.
5. D. S. Johnson. Fast algorithms for bin packing. Journal of Computer and System Sciences, 8(3):272–314, 1974.
6. C.-C. Lee and D.-T. Lee. A simple on-line bin-packing algorithm. J. ACM, 32(3):562–572, July 1985.
7. Y. Zhang, J. Chen, F. Y. L. Chin, X. Han, H.-F. Ting, and Y. H. Tsin. Improved online algorithms for 1-space bounded 2-dimensional bin packing. In O. Cheong, K.-Y. Chwa, and K. Park, editors, Algorithms and Computation, pages 242–253, Berlin, Heidelberg, 2010. Springer.
8. Y. Zhang, F. Y. L. Chin, and H.-F. Ting. One-space bounded algorithms for two-dimensional bin packing. International Journal of Foundations of Computer Science, 21(06):875–891, 2010.
9. Y. Zhang, F. Y. L. Chin, H.-F. Ting, and X. Han. Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing. Journal of Combinatorial Optimization, 26(2):223–236, 2013.