Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing

DOI10.1287/moor.1040.0112zbMath1082.90141OpenAlexW2097115415MaRDI QIDQ5704216

Michele Monaci, Alberto Caprara, Andrea Lodi

Publication date: 11 November 2005

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.1040.0112

zbMATH Keywords

two-dimensional bin packingtwo-dimensional strip packingasymptotic fully polynomial time approximation schemefractional two-dimensional bin packingtwo-stage packing

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Packing Cubes into a Cube in (D>3)-Dimensions, Approximation and online algorithms for multidimensional bin packing: a survey, Tight approximation algorithms for geometric bin packing with skewed items, Packing Rectangles into 2OPT Bins Using Rotations, An approximation scheme for the two-stage, two-dimensional knapsack problem, Absolute approximation ratios for packing rectangles into bins, A family of heuristic-based inequalities for maximizing overall safety margins in aircraft parking stands arrangement problems, Packing, covering and tiling in two-dimensional spaces, Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation, On Guillotine Separability of Squares and Rectangles., Online square-into-square packing, Bidimensional packing by bilinear programming, Approximation algorithms for orthogonal packing problems for hypercubes, Packing cubes into a cube is NP-complete in the strong sense