A new lower bound for online strip packing

DOI10.1016/J.EJOR.2015.10.012zbMATH Open1346.90724OpenAlexW2189948397MaRDI QIDQ322552FDOQ322552

Authors: Guosong Yu, Yanling Mao, Jiaoliao Xiao 

Publication date: 7 October 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2015.10.012

Recommendations

• Improved lower bound for online strip packing
• Improved Lower Bound for Online Strip Packing
• New upper bounds for online strip packing
• A lower bound for online rectangle packing
• A new upper bound for the online square packing problem in a strip

zbMATH Keywords

strip packingcompetitive ratioonline algorithmpacking

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• A near-optimal solution to a two-dimensional cutting stock problem
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A \((5/3+\varepsilon)\)-approximation for strip packing
• Lower bounds for on-line two-dimensional packing algorithms
• Shelf Algorithms for Two-Dimensional Packing Problems
• Orthogonal Packings in Two Dimensions
• A note on online strip packing
• A 2.5 times optimal algorithm for packing in two dimensions
• Improved lower bound for online strip packing
• A tight analysis of Brown-Baker-Katseff sequences for online strip packing
• Approximation algorithms for multiple strip packing
• Online Algorithm for Parallel Job Scheduling and Strip Packing
• Approximate algorithms to pack rectangles into several strips
• Online multiple-strip packing
• Scheduling parallel jobs to minimize the makespan
• Online scheduling of parallel jobs on two machines is 2-competitive

Cited In (12)

• New upper bounds for online strip packing
• Exact solution techniques for two-dimensional cutting and packing
• Online strip packing with modifiable boxes
• A new upper bound for the online square packing problem in a strip
• On online algorithms for bin, strip, and box packing, and their worst-case and average-case analysis
• Improved Lower Bound for Online Strip Packing
• A note on online strip packing
• Online scheduling of moldable parallel tasks
• Online strip packing with polynomial migration
• A lower bound for online rectangle packing
• 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: A new lower bound for online strip packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322552)