Tight bounds for online class-constrained packing

DOI10.1016/J.TCS.2003.05.006zbMATH Open1067.90144OpenAlexW2171709162MaRDI QIDQ596145FDOQ596145

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

Recommendations

• scientific article; zbMATH DE number 2086257
• The Class Constrained Bin Packing Problem with Applications to Video-on-Demand
• The class constrained bin packing problem with applications to video-on-demand
• scientific article; zbMATH DE number 1670546
• Online bin packing with cardinality constraints resolved

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) Combinatorial aspects of packing and covering (05B40) Discrete location and assignment (90B80)

Cites Work

• Title not available (Why is that?)
• Online algorithms. The state of the art
• Cardinality constrained bin-packing problems
• Fair versus unrestricted bin packing
• Fast algorithms for bin packing
• New Algorithms for Bin Packing
• Approximation algorithms for knapsack problems with cardinality constraints
• On-line load balancing
• Polynomial time approximation schemes for class-constrained packing problems
• Design and implementation of scalable continuous media servers
• Title not available (Why is that?)
• On two class-constrained versions of the multiple knapsack problem
• Multiprocessor scheduling with machine allotment and parallelism constraints
• The accommodating function: A generalization of the competitive ratio
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On-Line Load Balancing of Temporary Tasks on Identical Machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Asymptotic Worst Case Behavior of Harmonic Fit

Cited In (18)

• Selfish bin coloring
• Class constrained bin covering
• The class constrained bin packing problem with applications to video-on-demand
• Title not available (Why is that?)
• The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
• Polynomial time approximation schemes for class-constrained packing problems
• Lower bounds for several online variants of bin packing
• Title not available (Why is that?)
• Resource Allocation Games with Multiple Resource Classes
• A one-dimensional bin packing problem with shelf divisions
• The constrained compartmentalized knapsack problem: mathematical models and solution methods
• The Class Constrained Bin Packing Problem with Applications to Video-on-Demand
• Probabilistic analysis of online (class-constrained) bin packing and bin covering
• Class constrained bin packing revisited
• Bin packing with directed stackability conflicts
• Comparing online algorithms for bin packing problems
• Bounds for online bin packing with cardinality constraints
• A note on dual approximation algorithms for class constrained bin packing problems

Uses Software

• Knapsack

This page was built for publication: Tight bounds for online class-constrained packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q596145)