Tight bounds for online class-constrained packing

DOI10.1016/J.TCS.2003.05.006MaRDI QIDQ596145zbMATH OpenOpenAlexFDO

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

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

Cites work

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

Cited in

(17)

• scientific article; zbMATH DE number 2086257 (Why is no real title available?)
• A one-dimensional bin packing problem with shelf divisions
• Comparing online algorithms for bin packing problems
• The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
• The class constrained bin packing problem with applications to video-on-demand
• Bounds for online bin packing with cardinality constraints
• Class constrained bin packing revisited
• Selfish bin coloring
• A note on dual approximation algorithms for class constrained bin packing problems
• scientific article; zbMATH DE number 1670546 (Why is no real title available?)
• Class constrained bin covering
• The constrained compartmentalized knapsack problem: mathematical models and solution methods
• Polynomial time approximation schemes for class-constrained packing problems
• The Class Constrained Bin Packing Problem with Applications to Video-on-Demand
• Probabilistic analysis of online (class-constrained) bin packing and bin covering
• Bin packing with directed stackability conflicts
• Resource allocation games with multiple resource classes

Describes a project that uses

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)