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.
2004
89
5
215
221
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]
B., Codenotti; G., DE MARCO; Leoncini, Mauro; Montangero, Manuela; M., Santini
File in questo prodotto:
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

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/305516
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 12
social impact