Research Institute for Discrete Mathematics, University of Bonn, Lennéstr. 2, 53113 Bonn, Germany
Abstract:
We formulate a generalization of the NP-complete rectangle packing problem by parameterizing it in terms of packing density, the ratio of rectangle areas, and the aspect ratio of individual rectangles. Then we show that almost all restrictions of this problem remain NP-complete and identify some cases where the answer to the decision problem can be found in constant time.