Cube packing

✍ Scribed by F.K. Miyazawa; Y. Wakabayashi

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 138 KB
• Volume: 297
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00647-3

✦ Synopsis

The Cube Packing Problem (CPP) is deÿned as follows. Find a packing of a given list of (small) cubes into a minimum number of (larger) identical cubes. We show ÿrst 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 o -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 deÿned and results on on-line and o -line algorithms are presented. The 2.669 result appears to be the best asymptotic bound currently known.