Online bin packing with cardinality constraints resolved

DOI10.4230/LIPICS.ESA.2017.10MaRDI QIDQ5111695zbMATH OpenFDO

Authors János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin

Publication date 27 May 2020

zbMATH Keywords

online algorithmslower boundsbin packingcardinality constraints

Mathematics Subject Classification ID

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

Recommendations

• Online bin packing with cardinality constraints resolved
• Bounds for online bin packing with cardinality constraints
• Improved lower bounds for the online bin packing problem with cardinality constraints
• Algorithms – ESA 2005
• Improved lower bounds for the online bin packing problem with cardinality constraints

Cites work

• scientific article; zbMATH DE number 566079 (Why is no real title available?)
• A simple on-line bin-packing algorithm
• AFPTAS results for common variants of bin packing: a new method for handling the small items
• Algorithms for on-line bin-packing problems with cardinality constraints
• An improved lower bound for on-line bin packing algorithms
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Approximation schemes for machine scheduling with resource (in-)dependent processing times
• Approximation schemes for ordered vector packing problems
• Bounds for online bin packing with cardinality constraints
• Cardinality constrained bin-packing problems
• Improved lower bounds for the online bin packing problem with cardinality constraints
• New Algorithms for Bin Packing
• New lower bounds for certain classes of bin packing algorithms
• On the online bin packing problem
• On-line bin packing in linear time
• Online Bin Packing with Cardinality Constraints
• Online lower bounds via duality
• Packing small vectors
• Resource constrained scheduling as generalized bin packing
• Tight bounds for online vector bin packing
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(17)

• Algorithms – ESA 2005
• Colored bin packing: online algorithms and lower bounds
• Several methods of analysis for cardinality constrained bin packing
• Tight bounds for online class-constrained packing
• The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
• scientific article; zbMATH DE number 2086257 (Why is no real title available?)
• scientific article; zbMATH DE number 2081032 (Why is no real title available?)
• Online Bin Packing with Cardinality Constraints
• Cardinality constrained bin-packing problems
• Online bin packing with cardinality constraints resolved
• Online bin packing with arbitrary release times
• Improved lower bounds for the online bin packing problem with cardinality constraints
• Improved lower bounds for the online bin packing problem with cardinality constraints
• Lower bounds for online bin covering-type problems
• A lower bound for online rectangle packing
• Bounds for online bin packing with cardinality constraints
• All-Around Near-Optimal Solutions for the Online Bin Packing Problem

This page was built for publication: Online bin packing with cardinality constraints resolved

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