On-line Packing Cubes into n Unit Cubes

• Autorzy: Zielonka Ł.

Identyfikatory

DOI

10.4064/ba8063-10-2016

• Języki publikacji: EN

Abstrakty

EN

If n ≥ 3 and d ∈ {3,4} or if n ≥ 1 and d ≥ 5, then any sequence of d-dimensional cubes of edge lengths not greater than 1 whose total volume does not exceed (n+1)⋅2^−d can be on-line packed into n unit d-dimensional cubes.

Słowa kluczowe

EN

on-line packing; cubes

• Wydawca: Instytut Matematyczny PAN
• Czasopismo: Bulletin of the Polish Academy of Sciences. Mathematics
• Rocznik: 2016
• Tom: Vol. 64, no. 2/3
• Strony: 185--198
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Zielonka Ł.

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

Bibliografia

• [1] K. Böröczky, Jr., Finite Packing and Covering, Cambridge Tracts in Math. 154, Cambridge Univ. Press, Cambridge, 2004.
• [2] B. Brubach, Improved online square-into-square packing, arXiv: 1401.5583 (2014).
• [3] B. Brubach, Improved bound for online square-into-square packing, in: Proc. 12th Workshop on Approximation and Online Algorithms (WAOA), 2014, 47–58.
• [4] S. Fekete and H. Hoffmann, Online Square-into-Square Packing, in: Proc. 16th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2013, 126–141.
• [5] G. Fejes Tóth and W. Kuperberg, Packing and covering with convex sets, in: Handbook of Convex Geometry, P. M. Gruber and J. M. Wills (eds.), North-Holland, 1993, 799–860.
• [6] X. Han, K. Iwama and G. Zhang, Online removable square packing, Theory Comput. Systems 43 (2008), 38–55.
• [7] J. Januszewski, On-line packing squares into n unit squares, Bull. Polish Acad. Sci. Math. 56 (2010) 137–145.
• [8] J. Januszewski and M. Lassak, On-line packing sequences of cubes in the unit cube, Geom. Dedicata 67 (1997), 285–293.
• [9] M. Lassak, A survey of algorithms for on-line packing and covering by sequences of convex bodies, in: Intuitive Geometry (Budapest, 1995), Bolyai Soc. Math. Stud. 6, János Bolyai Math. Soc., Budapest, 1997, 129–157.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.