Cardinality constrained bin-packing problems

We are concerned with a variant of the classical one-dimensional bin-packing problem. n items have to be packed into unit-capacity bins such that the total number of used bins is minimized with the additional constraint that at most k items can be assigned to one bin. In 1975, Krause et al. analyzed...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 1999-01, Vol.92, p.335
Main Authors: Kellerer, Hans, Pferschy, Ulrich
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Heuristic
Operations research
Packing problem
Studies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We are concerned with a variant of the classical one-dimensional bin-packing problem. n items have to be packed into unit-capacity bins such that the total number of used bins is minimized with the additional constraint that at most k items can be assigned to one bin. In 1975, Krause et al. analyzed several approximation algorithms for this problem and showed that they all have an asymptotic worst-case performance ratio of 2. No better algorithms have been found so far. We present a new heuristic with an asymptotic worst-case bound of 3y2 and O(n log2 n) running time. [PUBLICATION ABSTRACT]
ISSN:0254-5330
1572-9338
DOI:10.1023/a:1018947117526