HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, August 6, 2014 - 4:24:39 PM
Last modification on : Thursday, February 7, 2019 - 3:08:45 PM
Long-term archiving on: : Wednesday, November 26, 2014 - 12:55:45 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Fouad B. Chedid. On Packing Splittable Items with Cardinality Constraints. 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. pp.101-110, ⟨10.1007/978-3-642-15240-5_8⟩. ⟨hal-01054441⟩



Record views


Files downloads