The problem of determining whether a set of rectangles can be orthogonally packed into a larger rectangle has been studied as a geometric packing problem and as a floor planning problem. Recently, there is some renewed interest in this problem, as it is related to a job scheduling problem in a partitionable mesh connected system. In this paper we show that the problem of deciding whether a set of squares can be packed into a larger square is strongly NP-complete, answering an open question posed by Li and Cheng.
All Science Journal Classification (ASJC) codes
- Artificial Intelligence
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications