Lower Bound for the Online Bin Packing Problem with Restricted Repacking

DOI10.1137/050647049MaRDI QIDQ3614164zbMATH OpenOpenAlexFDO

Authors János Balogh, József Békési, Gábor Galambos, Gerhard Reinelt

Publication date 16 March 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/a8fd1e3f45576d7cbc3f4618baaa23b7e83a2ced

zbMATH Keywords

bin packinglower boundsemi-online algorithmworst-case behavior

Mathematics Subject Classification ID

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

Recommendations

• An improved lower bound for on-line bin packing algorithms
• Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
• On-line bin packing with restricted repacking
• A new lower bound for classic online bin packing
• An \(\frac{8}{3}\) lower bound for online dynamic bin packing

Cited in

(7)

• Improved lower bounds for semi-online bin packing problems
• Dynamic bin packing with unit fraction items revisited
• Fully dynamic bin packing revisited
• On-line bin packing with restricted repacking
• Semi-on-line bin packing: a short overview and a new lower bound
• Fully-dynamic bin packing with little repacking
• A robust AFPTAS for online bin packing with polynomial migration

This page was built for publication: Lower Bound for the Online Bin Packing Problem with Restricted Repacking

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