We study harmonic-based algorithms for the d-dimensional (dD) generalizations of three classical geometric packing problems: geometric bin packing (BP), strip packing (SP), and geometric knapsack (KS) . Caprara (MOR 2008) studied a harmonic-based algorithm \mathtt{HDH an asymptotic approximation ratio  of T_{\infty}^{d-1} (where T_{\infty} \approx 1.691) for dD BP and dD SP when items are not allowed to be rotated. We give fast and simple harmonic-based algorithms with asymptotic approximation ratios of T_{\infty^{d-1}, T_{\infty}^{d} and (1-\epsilon)3^{-d} for dD SP, dD BP and dD KS, respectively, when orthogonal rotations are allowed }  about all or a subset of axes. This gives the first approximation algorithm for dD KS for d > 3. Furthermore, we provide a more sophisticated harmonic-based algorithm, which we call HGaP_k, that is T_{\infty}^{d-1}(1+\epsilon) -asymptotic-approximate for dD BP for the rotational case . This gives an approximation ratio of 2.860 + \epsilon for 3D BP with rotations, which improves upon the current best-known algorithm . In addition, we study  multiple-choice packing problems that generalize the rotational case. Here we are given n sets of dD cuboidal items and we have to choose exactly one (resp. at most one for the knapsack variant) item from each set and then pack the chosen items. All our algorithms also work for  multiple-choice packing problems .
We explore approximation algorithms for the d-dimensional geometric bin packing problem (dBP) . Caprara (MOR 2008) gave a harmonic-based algorithm for dBP having an asymptotic approximation ratio (AAR) of T_{\infty}^{d-1} (where T_{\infty} \approx 1.691) . However, their algorithm doesn't allow items to be rotated. ^{d-1}, T_{\infty}^{d} and (1-\epsilon)3^{-d} for dD SP, dD BP and dD KS, respectively, when orthogonal rotations are allowed } 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_{\infty a more sophisticated harmonic-based algorithm, which we call HGaP_k, having AAR T_{\infty}^{d-1}(1+\epsilon) . This gives an AAR of roughly 2.860 + \epsilon 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 .
R
study harmonic-based
explore approximation
R
(dD) generalizations of three classical geometric packing problems: geometric bin packing (BP), strip packing (SP), and geometric knapsack (KS)
geometric bin packing problem (dBP)
R
studied
gave
R
\mathtt{HDH
for dBP having
A
(AAR)
R
for dD BP and dD SP when items are not allowed
. However, their algorithm doesn't allow items
D
We give fast and simple harmonic-based algorithms with asymptotic approximation ratios of T_{\infty
A
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
R
This gives the first approximation algorithm for dD KS for d > 3. Furthermore, we provide
We first give a fast and simple harmonic-based algorithm having AAR T_{\infty
R
that is
having AAR
D
-asymptotic-approximate for dD BP for the rotational case
R
approximation ratio of
AAR of roughly
R
3D BP
3BP
D
current
R
algorithm
AAR of 4.5
A
the
R
packing problems that generalize
bin packing problem that generalizes
R
dD
d-dimensional
D
(resp. at most one for the knapsack variant)
R
All our
Our
A
the
R
packing problems
bin packing problem. We also give fast and simple approximation algorithms for the multiple-choice versions of dD strip packing and dD geometric knapsack