Bounds for online bin packing with cardinality constraints

DOI10.1016/j.ic.2016.06.001zbMath1344.68288OpenAlexW2419220708MaRDI QIDQ2629856

Leah Epstein, József Békési, György Dósa

Publication date: 7 July 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.06.001

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

Related Items

Lower bounds for batched bin packing, The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints, A note on a variant of the online open end bin packing problem, Online bin packing with cardinality constraints resolved, Lower bounds for several online variants of bin packing, A new lower bound for classic online bin packing, Several methods of analysis for cardinality constrained bin packing, Unnamed Item, More on ordered open end bin packing, A lower bound for online rectangle packing, Several methods of analysis for cardinality constrained bin packing

Cites Work

• Unnamed Item
• New lower bounds for certain classes of bin packing algorithms
• On the absolute approximation ratio for first fit and related results
• Tight bounds for online class-constrained packing
• Class constrained bin packing revisited
• A lower bound for on-line bin packing
• An improved lower bound for on-line bin packing algorithms
• Resource constrained scheduling as generalized bin packing
• Polynomial time approximation schemes for class-constrained packing problems
• Fast algorithms for bin packing
• Algorithms for on-line bin-packing problems with cardinality constraints
• Cardinality constrained bin-packing problems
• Improved lower bounds for the online bin packing problem with cardinality constraints
• The class constrained bin packing problem with applications to video-on-demand
• AFPTAS Results for Common Variants of Bin Packing: A New Method for Handling the Small Items
• On the online bin packing problem
• A simple on-line bin-packing algorithm
• New Algorithms for Bin Packing
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Approximation schemes for ordered vector packing problems
• On-line bin packing in linear time
• The optimal absolute ratio for online bin packing
• Online Bin Packing with Cardinality Constraints