An algorithm for 1-space bounded cube packing

• Autorzy: Zielonka Łukasz

Identyfikatory

DOI

10.15439/2019F88

• Konferencja: Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

on-line algorithm; bin packing; cube; one-space bounded

PL

algorytm online; pakowanie; sześcian

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2019
• Tom: Vol. 18
• Strony: 171--175
• Opis fizyczny: Bibliogr. 9 poz., wz., rys.

Twórcy

autor

Zielonka Łukasz

• Institute of Mathematics and Physics, UTP University of Science and Technology, Al. Prof. S. Kaliskiego 7, 85-789 Bydgoszcz, Poland

Bibliografia

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

Uwagi

1. Track 1: Artificial Intelligence and Applications

2. Technical Session: 12th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).