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

Authors:
  • BBB. S. Baker
    B. S. Baker
  • ACA. R. Calderbank
    A. R. Calderbank
  • JCJr. E. G. Coffman
    Jr. E. G. Coffman
  • JLJ. C. Lagarias
    J. C. Lagarias

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.

This publication has 12 references indexed in Scilit: