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; Leoncini, Mauro; Montangero, Manuela; M., Santini. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 89:5(2004), pp. 215-221. [10.1016/j.ipl.2003.12.001]
Approximation algorithms for a hierarchically structured bin packing problem
LEONCINI, Mauro;MONTANGERO, Manuela;
2004
Abstract
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
ipl04.pdf
Accesso riservato
Tipologia:
Versione originale dell'autore proposta per la pubblicazione
Dimensione
159.93 kB
Formato
Adobe PDF
|
159.93 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
