Please use this identifier to cite or link to this item:
|Type:||Artigo de evento|
|Abstract:||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. © Springer-Verlag Berlin Heidelberg 2000.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.