On Packing Splittable Items with Cardinality Constraints

Abstract : This paper continues the study of the the allocation of memory to processors in a pipeline problem. This problem can be modeled as a variation of bin packing where each item corresponds to a different type and the normalized weight of each item can be greater than 1, which is the size of a bin. Furthermore, in this problem, items may be split arbitrarily, but each bin may contain at most k types of items, for any fixed integer k ≥ 2. The case of k = 2 was first introduced by Chung el al. who gave a 3/2-approximation asymptotically. In this paper, we generalize the result of Chung et al. to higher k. We show that NEXT FIT gives a $\left(1+\frac 1 k\right)$-approximation asymptotically, for k ≥ 2. Also, as a minor contribution, we rewrite the strong NP-hardness proof of Epstein and van Stee for this problem for k ≥ 3.
Type de document :
Communication dans un congrès
Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.101-110, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_8〉
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054441
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 août 2014 - 16:24:39
Dernière modification le : mercredi 9 août 2017 - 12:03:18
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 00:55:45

Fichier

03230101.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Fouad B. Chedid. On Packing Splittable Items with Cardinality Constraints. Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.101-110, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_8〉. 〈hal-01054441〉

Partager

Métriques

Consultations de la notice

89

Téléchargements de fichiers

62