Tight bounds for online class-constrained packing

DOI10.1016/j.tcs.2003.05.006zbMath1067.90144OpenAlexW2171709162MaRDI QIDQ596145

Hadas Shachnai, Tami Tamir

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Bin packingClass-constraintsMultiple knapsackOnline algorithmsTemporary assignment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Combinatorial aspects of packing and covering (05B40)

Related Items

Bounds for online bin packing with cardinality constraints ⋮ The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints ⋮ Selfish bin coloring ⋮ The constrained compartmentalized knapsack problem: mathematical models and solution methods ⋮ Comparing online algorithms for bin packing problems ⋮ Resource Allocation Games with Multiple Resource Classes ⋮ The class constrained bin packing problem with applications to video-on-demand ⋮ A one-dimensional bin packing problem with shelf divisions ⋮ Class constrained bin covering ⋮ Class constrained bin packing revisited ⋮ Lower bounds for several online variants of bin packing ⋮ A note on dual approximation algorithms for class constrained bin packing problems ⋮ Bin packing with directed stackability conflicts

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fair versus unrestricted bin packing
• Online algorithms. The state of the art
• Design and implementation of scalable continuous media servers
• On-line load balancing
• Polynomial time approximation schemes for class-constrained packing problems
• Multiprocessor scheduling with machine allotment and parallelism constraints
• Approximation algorithms for knapsack problems with cardinality constraints
• Fast algorithms for bin packing
• Cardinality constrained bin-packing problems
• The Accommodating Function: A Generalization of the Competitive Ratio
• New Algorithms for Bin Packing
• On-Line Load Balancing of Temporary Tasks on Identical Machines
• On the Asymptotic Worst Case Behavior of Harmonic Fit
• On two class-constrained versions of the multiple knapsack problem