Cube Packing

The Cube Packing Problem (CPP) is defined as follows. Find a packing of a given list of (small) cubes into a minimum number of (larger) identical cubes. We show first that the approach introduced by Coppersmith and Raghavan for general online algorithms for packing problems leads to an online algorithm for CPP with asymptotic performance bound 3.954. Then we describe two other offline approximation algorithms for CPP: one with asymptotic performance bound 3.466 and the other with 2.669. A parametric version of this problem is defined and results on online and offline algorithms are presented. We did not find in the literature offline algorithms with asymptotic performance bounds as good as 2.669.

1999