Approximation Algorithms for a Hierachically Structured Bin Packing Problem

Codenotti, B.; DE MARCO, Gianluca; Leoncini, M.; Montangero, M.; Santini, M.

UniSa - IRIS Institutional Research Information System

IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.

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 Hierachically Structured Bin Packing Problem
Autori:	B. CODENOTTI DE MARCO, Gianluca M. LEONCINI M. MONTANGERO M. SANTINI mostra contributor esterni nascondi contributor esterni
Data di pubblicazione:	2004
Rivista:	INFORMATION PROCESSING LETTERS
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.
Handle:	http://hdl.handle.net/11386/1000495
Appare nelle tipologie:	1.1.2 Articolo su rivista con ISSN

File in questo prodotto:

Non ci sono file associati a questo prodotto.

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/11386/1000495

Citazioni

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.