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 algorithmsNP-hardtwo-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)

Cited in

(26)

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

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)