Algorithms for on-line bin-packing problems with cardinality constraints

DOI10.1016/J.DAM.2003.05.006zbMath1077.68115OpenAlexW1994243396MaRDI QIDQ1887058

Luitpold Babel, Hans Kellerer, Bo Chen, Vladimir Kotov

Publication date: 23 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.05.006

zbMATH Keywords

On-line algorithmsBin packingCardinality constraint

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27)

Related Items (29)

Models for video-on-demand scheduling with costs ⋮ Bounds for online bin packing with cardinality constraints ⋮ The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints ⋮ An improved typology of cutting and packing problems ⋮ Selfish bin packing with cardinality constraints ⋮ Online bin packing with cardinality constraints resolved ⋮ EPTAS for the dual of splittable bin packing with cardinality constraint ⋮ Approximation schemes for packing splittable items with cardinality constraints ⋮ Improved results for a memory allocation problem ⋮ Colored bin packing: online algorithms and lower bounds ⋮ Unnamed Item ⋮ Bin covering with cardinality constraints ⋮ An efficient algorithm for bin stretching ⋮ Online bin stretching with bunch techniques ⋮ Online unit clustering: Variations on a theme ⋮ Online interval coloring with packing constraints ⋮ Class constrained bin covering ⋮ Class constrained bin packing revisited ⋮ Unnamed Item ⋮ Constructive heuristics for the canister filling problem ⋮ Lower bounds for several online variants of bin packing ⋮ Approximation Schemes for Packing Splittable Items with Cardinality Constraints ⋮ Online cardinality constrained scheduling ⋮ Tighter bounds for the harmonic bin packing algorithm ⋮ A new lower bound for classic online bin packing ⋮ Several methods of analysis for cardinality constrained bin packing ⋮ Unnamed Item ⋮ Several methods of analysis for cardinality constrained bin packing ⋮ Improved lower bounds for the online bin packing problem with cardinality constraints

Cites Work

• Unnamed Item
• Online algorithms. The state of the art
• Improved bounds for harmonic-based bin packing algorithms
• An improved lower bound for on-line bin packing algorithms
• Resource constrained scheduling as generalized bin packing
• A simple on-line bin-packing algorithm
• New Algorithms for Bin Packing
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Approximation schemes for ordered vector packing problems

This page was built for publication: Algorithms for on-line bin-packing problems with cardinality constraints