scientific article; zbMATH DE number 7204988

DOI10.4230/LIPIcs.ESA.2017.10zbMath1442.68268MaRDI QIDQ5111695

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

Publication date: 27 May 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

online algorithmslower boundscardinality constraintsbin packing

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

The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints ⋮ Colored bin packing: online algorithms and lower bounds ⋮ Lower bounds for several online variants of bin packing ⋮ Lower bounds for online bin covering-type problems ⋮ A lower bound for online rectangle packing

Cites Work

• Unnamed Item
• New lower bounds for certain classes of bin packing algorithms
• An improved lower bound for on-line bin packing algorithms
• Resource constrained scheduling as generalized 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
• Bounds for online bin packing with cardinality constraints
• 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
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Approximation schemes for ordered vector packing problems
• Packing Small Vectors
• Approximation schemes for machine scheduling with resource (in-)dependent processing times
• Online Lower Bounds via Duality
• On-line bin packing in linear time
• Online Bin Packing with Cardinality Constraints
• Tight bounds for online vector bin packing