The Library
On-line algorithms for cardinality constrained bin packing problems
Tools
UNSPECIFIED (2001) On-line algorithms for cardinality constrained bin packing problems. In: 12th Annual International Symposium on Algorithms and Computation, CHRISTCHURCH, NEW ZEALAND, DEC 19-21, 2001. Published in: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2223 pp. 695-706. ISBN 3-540-42985-9. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 | ||||
Official Date: | 2001 | ||||
Dates: |
|
||||
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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |