Approximate strip packing: revisited

DOI10.1016/j.ic.2016.03.010zbMath1345.68275MaRDI QIDQ2629852

Xin Han, Deshi Ye, Kazuo Iwama, Guo-Chuan Zhang

Publication date: 7 July 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.03.010

zbMATH Keywords

approximation algorithms; strip packing; harmonic algorithms

Mathematics Subject Classification ID

90C27: Combinatorial optimization

68W25: Approximation algorithms

Related Items

Exact solution techniques for two-dimensional cutting and packing, The variable-width strip packing problem, A deep reinforcement learning based hyper-heuristic for combinatorial optimisation with uncertainties, Approximation and online algorithms for multidimensional bin packing: a survey

Cites Work

• Unnamed Item
• Shelf algorithms for on-line strip packing
• Improved bounds for harmonic-based bin packing algorithms
• A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
• An improved lower bound for on-line bin packing algorithms
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• On the online bin packing problem
• Shelf Algorithms for Two-Dimensional Packing Problems
• A new proof for the first-fit decreasing bin-packing algorithm
• A simple on-line bin-packing algorithm
• New Algorithms for Bin Packing
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
• A algorithm for two-dimensional packing
• On-line bin packing in linear time