Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms

DOI10.1007/BF02246509zbMath0817.90080OpenAlexW1580752931MaRDI QIDQ1332349

André van Vliet, Gábor Galambos

Publication date: 1 August 1995

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02246509

zbMATH Keywords

lower boundssuboptimal algorithms1-dimensional bin packingasymptotic worst case ratio

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items (11)

Semi-on-line bin packing: a short overview and a new lower bound ⋮ On two dimensional packing ⋮ Worst-case analysis of fast heuristics for packing squares into a square ⋮ Stochastic simulations of two-dimensional composite packings ⋮ On-line bin packing ? A restricted survey ⋮ New lower bounds for certain classes of bin packing algorithms ⋮ On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis ⋮ Online bin packing of squares and cubes ⋮ Online bin packing of squares and cubes ⋮ Two-dimensional online bin packing with rotation ⋮ A lower bound for online rectangle packing

Cites Work

• Unnamed Item
• Unnamed Item
• An on-line algorithm for multidimensional bin packing
• A lower bound for on-line bin packing
• An improved lower bound for on-line bin packing algorithms
• A simple proof of Liang's lower bound for on-line bin packing and the extension to the parametric case

This page was built for publication: Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms