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

https://hal.inria.fr/hal-01054441
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

File

03230101.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

63

Files downloads

131