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

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