Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/107293
Type: Artigo de periódico
Title: Multidimensional Cube Packing
Author: Kohayakawa Y.
Miyazawa F.K.
Raghavan P.
Wakabayashi Y.
Abstract: We consider the d-dimensional cube packing problem (d-CPP): given a list L of d-dimensional cubes and (an unlimited quantity of) d-dimensional unit-capacity cubes, called bins, find a packing of L into the minimum number of bins. We present two approximations algorithms for d-CPP, for fixed d. The first algorithm has an asymptotic performance bound that can be made arbitrarily close to 2 - 1/2d. The second algorithm is an improvement of the first and has an asymptotic performance bound that can be made arbitrarily close to 2 - (2/3)d. To our knowledge, these results improve the bounds known so far for d = 2 and d = 3, and are the first results with bounds that are not exponential in the dimension.
Editor: 
Rights: fechado
Identifier DOI: 
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-34247534283&partnerID=40&md5=75c55549df9c6defb7bec85982a73d89
Date Issue: 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.