Comments on the hierarchically structured bin packing problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Information Processing Letters Année : 2015

Comments on the hierarchically structured bin packing problem

Résumé

We study the hierarchically structured bin packing problem. In this problem, the items to be packed into bins are at the leaves of a tree. The objective of the packing is to minimize the total number of bins into which the descendants of an internal node are packed, summed over all internal nodes. We investigate an existing algorithm and make a correction to the analysis of its approximation ratio. Further results regarding the structure of an optimal solution and a strengthened inapproximability result are given.
Fichier principal
Vignette du fichier
article.pdf (1.88 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01071414 , version 1 (04-10-2014)
hal-01071414 , version 2 (08-10-2014)

Identifiants

Citer

Thomas Lambert, Loris Marchal, Bora Uçar. Comments on the hierarchically structured bin packing problem. Information Processing Letters, 2015, 115 (2), pp.306--309. ⟨10.1016/j.ipl.2014.10.001⟩. ⟨hal-01071414v2⟩
265 Consultations
426 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More