New Lower Bounds for Certain Classes of Bin Packing Algorithms

DOI10.1007/978-3-642-18318-8_3MaRDI QIDQ3075446zbMATH OpenOpenAlexWikidataFDO

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

Publication date 15 February 2011

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-18318-8_3

Mathematics Subject Classification ID

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

Recommendations

• New lower bounds for certain classes of bin packing algorithms
• scientific article; zbMATH DE number 1187157
• New classes of fast lower bounds for bin packing problems
• New bin packing fast lower bounds
• An improved lower bound for the bin packing problem
• A new lower bound for classic online bin packing
• A new lower bound for classic online bin packing
• A tight lower bound for optimal bin packing
• Lower bounds for batched bin packing
• Lower bounds and reduction procedures for the bin packing problem

Cited in

(18)

• Improved bounds for harmonic-based bin packing algorithms
• A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case
• Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
• A new lower bound on the price of anarchy of selfish bin packing
• Fully dynamic bin packing revisited
• NF-based algorithms for online bin packing with buffer and bounded item size
• On-line bin packing with restricted repacking
• NF-based algorithms for online bin packing with buffer and item size limitation
• Semi-on-line bin packing: a short overview and a new lower bound
• Bin packing with ``largest in bottom constraint: tighter bounds and generalizations
• New lower bounds for certain classes of bin packing algorithms
• scientific article; zbMATH DE number 3997164 (Why is no real title available?)
• Online square packing with gravity
• A new lower bound for classic online bin packing
• A new lower bound for classic online bin packing
• Station assignment with reallocation
• An asymptotic competitive scheme for online bin packing
• Lower bounds and reduction procedures for the bin packing problem

This page was built for publication: New Lower Bounds for Certain Classes of Bin Packing Algorithms

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