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 on-line algorithms for packing problems leads to an on-line algorithm for CPP with asymptotic performance bound 3.954. Then we describe two other off-line 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 on-line and off-line algorithms are presented. The 2.669 result appears to be the best asymptotic bound currently known. (C) 2002 Elsevier Science B.V. All rights reserved.
cube packing asymptotic performance approximation algorithms