Improved lower bound for online strip packing

DOI10.1007/s00224-013-9494-8zbMath1328.68316OpenAlexW1979060810MaRDI QIDQ2344211

Rolf Harren, Walter Kern

Publication date: 12 May 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9494-8

zbMATH Keywords

online algorithmslower boundsstrip packingrectangle packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

Related Items (6)

A new lower bound for online strip packing ⋮ A tight analysis of Brown-Baker-Katseff sequences for online strip packing ⋮ Parameterized complexity of strip packing and minimum volume packing ⋮ New upper bounds for online strip packing ⋮ A new upper bound for the online square packing problem in a strip ⋮ Improved lower bound for online strip packing

Cites Work

• Shelf algorithms for on-line strip packing
• Scheduling parallel jobs to minimize the makespan
• Online scheduling of parallel jobs on two machines is 2-competitive
• A note on online strip packing
• Lower bounds for on-line two-dimensional packing algorithms
• Online matching on a line
• Improved lower bound for online strip packing
• A tight analysis of Brown-Baker-Katseff sequences for online strip packing
• Shelf Algorithms for Two-Dimensional Packing Problems
• Orthogonal Packings in Two Dimensions
• Strip Packing vs. Bin Packing
• Online Algorithm for Parallel Job Scheduling and Strip Packing

This page was built for publication: Improved lower bound for online strip packing