On-line potato-sack algorithm efficient for packing into small boxes
type: Item
instance of: scholarly article
title: On-line potato-sack algorithm efficient for packing into small boxes
zbMATH Open document ID: 0892.52012
DOI: 10.1023/A:1004280725513
published in: Periodica Mathematica Hungarica
publication date: 1998-03-26T00:00:00Z
review text: The subject of packing sequences of convex bodies was initiated by Auerbach, Banach, Mazur and Ulam, cf. Problem 10.1, in The Scottish Book [ed. by \textit{R. D. Mauldin}, Birkhäuser, Boston (1981; Zbl 0485.01013)]. Their corollary that one kilogram of potatoes can be put into a finite sack caused that results of this kind are sometimes called potato-sack theorems. By a box in \(E^d\) we mean any set of the form \[ \{(x_1,\dots,x_d); r_j \leq x_j \leq s_j \;\text{for} j=1,\dots,d\}, \] with \(r_j< s_j\) for \(j=1,\dots,d\). The number \(s_j-r_j\), where \(j\in\{1,\dots,d\}\) is called the \(j\)-th width of this box. By the height of this box it means the \(d\)-th width. The set \(\{(x_1,\dots,x_d); r_j\leq x_j \leq s_j\) for \(j=1,\dots,d-1\) and \(x_d=y_d\}\) is called the bottom of this box for \(y_d=r_d\) and the top for \(y_d=s_d\). If \(r_1=\dots=r_d=0\), the box is denoted by symbol \(B(s_1,\dots,s_d)\). The cube \(B(s,\dots,s)\) is denoted by \(I^d_s\). It is known that every \(d\)-dimensional convex body of diameter \(1\) and volume \(v\) can be moved into a convenient box of volume at most \(d!v\) and edge lengths at most \(1\) [see \textit{H. Hadwiger}, Elem. Math. 10, 122-124 (1955; Zbl 0066.40605) or \textit{A. Kosiński}, Coll. Math. 4, 216-218 (1957; Zbl 0083.38041)]. This result reduces the problem of packing sequences of convex bodies of diameters at most \(1\) to the problem of packing sequences of boxes of edge lengths at most \(1\) that can be packed. Then immediately can be obtained \(d!\) times smaller estimates for packing sequences of convex bodies of diameters at most \(1\). If \(s_1>1,\dots,s_d>1\), then the translative method of layers presented in \textit{M. Lassak} and \textit{J. Zhang} [Discrete Comput. Geom. 6, 1-7 (1991; Zbl 0727.52004)] permits packing every sequences of boxes of edge lengths at most \(1\) with total volume at most \((s_1-1)\prod^d_{j=2}(s_j-1)^2\) in \(B(s_1,\dots,s_d)\). The aim of this paper is to show an on-line al…
Mathematics Subject Classification ID: 52C17
zbMATH DE Number: 1134675
zbMATH Keywords: on-line packing
zbMATH Keywords: box
zbMATH Keywords: cube
zbMATH Keywords: volume
author: Marek Lassak
MaRDI profile type: Publication
full work available at URL: a:1004280725513
OpenAlex ID: W1836402768
Recommended article: An on-line algorithm for multidimensional bin packing
Recommended article: An on-line algorithm for variable-sized bin packing
Recommended article: Online packing of \(d\)-dimensional boxes into the unit cube
Recommended article: Q3783565
Recommended article: Online square-into-square packing
Recommended article: On-line packing sequences of segments, cubes and boxes
Recommended article: On-line bin packing in linear time
Recommended article: On-line Packing Cubes into $n$ Unit Cubes
description: scientific article; zbMATH DE number 1134675