Lower bounds for on-line two-dimensional packing algorithms

DOI10.1007/BF00264439MaRDI QIDQ1168732zbMATH OpenOpenAlexFDO

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

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

approximation algorithmslower bounds for the worst-case performance of on-line algorithmsNP-hardtwo-dimensional bin packing

Mathematics Subject Classification ID

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

Cited in

(26)

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

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

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