Shelf algorithms for on-line strip packing

DOI10.1016/S0020-0190(97)00120-8zbMath1336.68305MaRDI QIDQ287167

Gerhard J. Woeginger, János A. Csirik

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00120-8

zbMATH Keywords

combinatorial problems; competitive analysis; online algorithms; analysis of algorithms; strip packing; worst case analysis

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C27: Combinatorial optimization

68W27: Online algorithms; streaming algorithms

Related Items

Unnamed Item, On-line algorithms for packing rectangles into several strips, Online strip packing with modifiable boxes, The generalization of scheduling with machine cost, Online square packing with gravity, Online multiple-strip packing, Strip packing with precedence constraints and strip packing with release times, On the effectiveness of the harmonic shelf algorithm for on-line strip packing, A note on online strip packing, The two-dimensional cutting stock problem revisited, The variable-width strip packing problem, On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis, Improved lower bound for online strip packing, Approximation and online algorithms for multidimensional bin packing: a survey, Approximate strip packing: revisited, Online Square Packing

Cites Work

• Lower bounds for on-line two-dimensional packing algorithms
• Improved bounds for harmonic-based bin packing algorithms
• An improved lower bound for on-line bin packing algorithms
• Shelf Algorithms for Two-Dimensional Packing Problems
• A simple on-line bin-packing algorithm
• Orthogonal Packings in Two Dimensions
• A algorithm for two-dimensional packing
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Two-Processor Scheduling with Start-Times and Deadlines