Algorithms for on-line bin-packing problems with cardinality constraints
UNSPECIFIED. (2004) Algorithms for on-line bin-packing problems with cardinality constraints. DISCRETE APPLIED MATHEMATICS, 143 (1-3). pp. 238-251. ISSN 0166-218XFull text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.dam.2003.05.006
The bin-packing problem asks for a packing of a list of items of sizes from (0, 1) into the smallest possible number of bins having unit capacity. The k-item bin-packing problem additionally imposes the constraint that at most k items are allowed in one bin. We present two efficient on-line algorithms for this problem. We show that, for increasing values of k, the bound on the asymptotic worst-case performance ratio of the first algorithm tends towards 2 and that the second algorithm has a ratio of 2. Both algorithms considerably improve upon the best known result of an algorithm, which has an asymptotic bound of 2.7 on its ratio. Moreover, we improve known bounds for all values of k by presenting on-line algorithms for k = 2 and 3 with bounds on their ratios close to optimal. (C) 2004 Elsevier B.V. All rights reserved.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics|
|Journal or Publication Title:||DISCRETE APPLIED MATHEMATICS|
|Publisher:||ELSEVIER SCIENCE BV|
|Date:||30 September 2004|
|Number of Pages:||14|
|Page Range:||pp. 238-251|
Actions (login required)