New upper bounds for online strip packing

DOI10.1016/J.DISOPT.2016.11.004zbMath1387.90231OpenAlexW2567592803MaRDI QIDQ1751205

Yanling Mao, Guosong Yu, Jiaoliao Xiao

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2016.11.004

zbMATH Keywords

competitive ratiopackingonline algorithmstrip packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Related Items (2)

Exact solution techniques for two-dimensional cutting and packing ⋮ Queue-constrained packing: a vehicle ferry case study

Cites Work

• A \((5/3+\varepsilon)\)-approximation for strip packing
• Online multiple-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
• A 2.5 times optimal algorithm for packing in two dimensions
• Lower bounds for on-line two-dimensional packing algorithms
• Improved lower bound for online strip packing
• A tight analysis of Brown-Baker-Katseff sequences for online strip packing
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Approximation Algorithms for Multiple Strip Packing
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• Shelf Algorithms for Two-Dimensional Packing Problems
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Orthogonal Packings in Two Dimensions
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Online Algorithm for Parallel Job Scheduling and Strip Packing
• Approximate algorithms to pack rectangles into several strips

This page was built for publication: New upper bounds for online strip packing