Improved lower bounds for semi-online bin packing problems

DOI10.1007/s00607-008-0023-6zbMath1165.68031OpenAlexW1996480689MaRDI QIDQ1014344

József Békési, Gábor Galambos, Mihály Csaba Markót, János Balogh

Publication date: 27 April 2009

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-008-0023-6

zbMATH Keywords

batched bin packing algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

Semi-on-line bin packing: a short overview and a new lower bound ⋮ Batch Coloring of Graphs ⋮ Fully-Dynamic Bin Packing with Little Repacking ⋮ Batch coloring of graphs

Uses Software

• PROFIL/BIAS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fundamental restriction on fully dynamic maintenance of bin packing
• More on online bin packing with two item sizes
• An improved lower bound for on-line bin packing algorithms
• Repacking helps in bounded space on-line bin-packing
• Handbook of global optimization
• Multisection in interval branch-and-bound methods for global optimization. II: Numerical tests
• Batched bin packing
• Algorithms for the Relaxed Online Bin-Packing Model
• On the online bin packing problem
• Lower Bound for the Online Bin Packing Problem with Restricted Repacking
• Dynamic Bin Packing
• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps

This page was built for publication: Improved lower bounds for semi-online bin packing problems