ABSTRACT
Two-dimensional packing problems involve packing a set of two-dimensional items into larger rectangular containers such that no item overlaps with each other. Items to be packed can take various shapes, such as the rectilinear blocks, raster graphics, and irregular polygons. These problems are classical combinatorial optimization problems and known to be NP-hard. Many packing problems are related to real-world applications in the wood, glass, steel, and leather industries, as well as in large-scale integration (LSI) and very-large-scale integration (VLSI) design and newspaper paging. They have been studied for a long time from both theoretical and practical points of view in various areas including operations research, computer science, and manufacturing.
