Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle

DOI10.1137/0604039zbMath0558.05002OpenAlexW2000902553MaRDI QIDQ3222847

Jeffrey C. Lagarias, Robert Calderbank, Brenda S. Baker, Edward G. jun. Coffman

Publication date: 1983

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0604039

zbMATH Keywords

NFIapproximation algorithmsBottom-Up-Increasing ruleBUIcomparison between algorithmsNext- Fit-Increasing rulepacking squares into a rectanglesubset problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Enumerative combinatorics (05A99) Combinatorial aspects of packing and covering (05B40) Designs and configurations (05B99)

Related Items (8)

Rectangle packing with one-dimensional resource augmentation ⋮ A lower bound for the non-oriented two-dimensional bin packing problem ⋮ 2D knapsack: packing squares ⋮ Cube packing. ⋮ Oriented aligned rectangle packing problem ⋮ Packing problems ⋮ Hardness of approximation for orthogonal rectangle packing and covering problems ⋮ PACKING SOFT RECTANGLES

Cites Work

• Bin packing: Maximizing the number of pieces packed
• A 2.5 times optimal algorithm for packing in two dimensions
• On packing squares with equal squares
• Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Orthogonal Packings in Two Dimensions
• A algorithm for two-dimensional packing
• On Packing Two-Dimensional Bins
• A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing

This page was built for publication: Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle