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

DOI10.1137/0604039zbMath0558.05002MaRDI 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

NFI; approximation algorithms; Bottom-Up-Increasing rule; BUI; comparison between algorithms; Next- Fit-Increasing rule; packing squares into a rectangle; subset problem

Mathematics Subject Classification ID

05A05: Permutations, words, matrices

05A99: Enumerative combinatorics

05B40: Combinatorial aspects of packing and covering

05B99: Designs and configurations

Related Items

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

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