A tight analysis of Brown-Baker-Katseff sequences for online strip packing

DOI10.1007/s10878-012-9463-1zbMath1275.90081OpenAlexW2152360290MaRDI QIDQ2392732

Walter Kern, Jacob Jan Paulus

Publication date: 2 August 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9463-1

zbMATH Keywords

competitive ratioonline algorithmstrip packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (5)

A new lower bound for online strip packing ⋮ The generalization of scheduling with machine cost ⋮ 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

• Unnamed Item
• 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
• Orthogonal Packings in Two Dimensions
• Online Algorithm for Parallel Job Scheduling and Strip Packing

This page was built for publication: A tight analysis of Brown-Baker-Katseff sequences for online strip packing