logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Cardinality constrained bin-packing problems

delete1999-01-01
delete40
PRE
AI
H
Hans Kellerer *
U
Ulrich Pferschy
DOI：10.1023/A:1018947117526delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
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 3/2 and O(n log(2) n) running time.
Keywords:
bin-packing
vector packing
worst-case analysis
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

Annals of Operations Research cover
Annals of Operations Research
IF:
4.5
Papers:
8.0K
Citations:
2.1W

Organization

No organization information available