Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle
Authors:
- B. S. BakerBBB. S. Baker
- A. R. CalderbankACA. R. Calderbank
- Jr. E. G. CoffmanJCJr. E. G. Coffman
- J. C. LagariasJLJ. C. Lagarias
- 1 September 1983
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 4 (3) , 383-397
Abstract
We consider the NP-hard problem of packing into a specified rectangle a maximum number of squares from a given set. We define two related approximation algorithms and derive bounds on the worst case performance of the packings they produce.Keywords
This publication has 12 references indexed in Scilit:
- On Packing Two-Dimensional BinsSIAM Journal on Algebraic Discrete Methods, 1982
- A 54 algorithm for two-dimensional packingJournal of Algorithms, 1981
- A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-PackingSIAM Journal on Algebraic Discrete Methods, 1981
- Approximation Algorithms for Bin Packing Problems: A Survey1981
- Orthogonal Packings in Two DimensionsSIAM Journal on Computing, 1980
- Performance Bounds for Level-Oriented Two-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1980
- Combinatorial Analysis of an Efficient Algorithm for Processor and Storage AllocationSIAM Journal on Computing, 1979
- Mathematical GamesScientific American, 1979
- Bin packing: Maximizing the number of pieces packedActa Informatica, 1978
- On packing squares with equal squaresJournal of Combinatorial Theory, Series A, 1975