Lower bounds for on-line two-dimensional packing algorithms

DOI10.1007/BF00264439zbMath0493.68042OpenAlexW1972899329MaRDI QIDQ1168732

Brenda S. Baker, Howard P. Katseff, Donna J. Brown

Publication date: 1982

Published in: Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

NP-hardapproximation algorithmstwo-dimensional bin packinglower bounds for the worst-case performance of on-line algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of packing and covering (05B40)

Related Items (26)

Shelf algorithms for on-line strip packing ⋮ Multiple-type, two-dimensional bin packing problems: Applications and algorithms ⋮ The nesting problem in the leather manufacturing industry ⋮ A new lower bound for online strip packing ⋮ A tight analysis of Brown-Baker-Katseff sequences for online strip packing ⋮ Efficient heuristics for robot acquisition planning for a CIM system ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ On-line bin packing ? A restricted survey ⋮ The generalization of scheduling with machine cost ⋮ A squeaky wheel optimisation methodology for two-dimensional strip packing ⋮ An asymptotic competitive scheme for online bin packing ⋮ An improved BL lower bound ⋮ Improved online algorithms for parallel job scheduling and strip packing ⋮ Unnamed Item ⋮ Online square packing with gravity ⋮ Oriented aligned rectangle packing problem ⋮ On-line scheduling of parallel jobs in a list ⋮ Knowledge based approach to the cutting stock problem ⋮ New upper bounds for online strip packing ⋮ The online graph bandwidth problem ⋮ On some packing problem related to dynamic storage allocation ⋮ A new upper bound for the online square packing problem in a strip ⋮ Online strip packing with modifiable boxes ⋮ On-line scheduling of multi-core processor tasks with virtualization ⋮ A note on online strip packing ⋮ Improved lower bound for online strip packing

This page was built for publication: Lower bounds for on-line two-dimensional packing algorithms