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.
Approximation Algorithms for a Hierarchically Structured Bin Packing Problem / B. Codenotti, G. De Marco, M. Leoncini, M. Montagero, M. Santini. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 89:5(2004 Mar), pp. 215-221.
Titolo: | Approximation Algorithms for a Hierarchically Structured Bin Packing Problem |
Autori: | SANTINI, MASSIMO (Ultimo) |
Parole Chiave: | Algorithms ; Approximation algorithms ; Bin packing ; NP-hardness |
Data di pubblicazione: | mar-2004 |
Rivista: | |
Tipologia: | Article (author) |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.ipl.2003.12.001 |
Appare nelle tipologie: | 01 - Articolo su periodico |
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.