UNSPECIFIED (2001) On-line algorithms for cardinality constrained bin packing problems. In: 12th Annual International Symposium on Algorithms and Computation, DEC 19-21, 2001, CHRISTCHURCH, NEW ZEALAND.

Full text not available from this repository.

Abstract

The bin packing problem asks for a packing of a list of items 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 approximation algorithms for the on-line version of this problem. We show that, for increasing values of k, the asymptotic worst-case performance ratio of the first algorithm tends towards 2 and that the second algorithm has an asymptotic worst-case performance ratio of 2. Both heuristics considerably improve upon the best known result 2.7 of Krause, Shen and Schwetman. Moreover, we present algorithms for k = 2 and k = 3, where the result for k = 2 is best possible.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Series Name:	LECTURE NOTES IN COMPUTER SCIENCE
Journal or Publication Title:	ALGORITHMS AND COMPUTATION, PROCEEDINGS
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	3-540-42985-9
ISSN:	0302-9743
Editor:	Eades, P and Takaoka, T
Date:	2001
Volume:	2223
Number of Pages:	12
Page Range:	pp. 695-706
Publication Status:	Published
Title of Event:	12th Annual International Symposium on Algorithms and Computation
Location of Event:	CHRISTCHURCH, NEW ZEALAND
Date(s) of Event:	DEC 19-21, 2001
URI:	http://wrap.warwick.ac.uk/id/eprint/11162

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item