In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the problem is NP-hard and we give approximation algorithms for the general case and for the particular case in which all the items have the same size.
|Titolo:||Approximation Algorithms for a Hierarchically Structured Bin Packing Problem|
|Autori interni:||SANTINI, MASSIMO (Ultimo)|
|Parole Chiave:||Algorithms ; Approximation algorithms ; Bin packing ; NP-hardness|
|Data di pubblicazione:||mar-2004|
|Digital Object Identifier (DOI):||10.1016/j.ipl.2003.12.001|
|Appare nelle tipologie:||01 - Articolo su periodico|