Shelf algorithms for on-line strip packing

DOI10.1016/S0020-0190(97)00120-8zbMath1336.68305OpenAlexW2055717964MaRDI 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 problemscompetitive analysisonline algorithmsanalysis of algorithmsstrip packingworst case analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (16)

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

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

This page was built for publication: Shelf algorithms for on-line strip packing