Computational Aspects of Packing Problems

Abstract

Packing problems have been investigated in mathematics since centuries. For polygons, circles, or other objects bounded by algebraic curves or surfaces it can be argued that packing problems are computable. However, even some of the simplest versions in the plane turn out to be NP-hard unless the number of objects to be packed is bounded. This article is a survey on results achieved about computability and complexity of packing problems, about approximation algorithms, and about very natural packing problems whose computational complexity is unknown.
Packing objects is a quite natural problem and has been investigated in mathematics and operations research for a long time. Applications concern the physical nonoverlapping packing of concrete objects during storage or transportation but also in two dimensions how to eciently cut prescribed pieces from cloth or sheet metal while minimizing waste. Even more abstract problems like, e.g., ecient scheduling with respect to time and space can be modelled as packing rectangles into a strip.