Packing Problem
Packing problems are a class of optimization problems in mathematics which involve attempting to pack objects together (often inside a container), as densely as possible. Many of these problems can be related to real life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.
In a packing problem, you are given:
- 'containers' (usually a single two- or three-dimensional convex region, or an infinite space)
- 'goods' (usually a single type of shape), some or all of which must be packed into this container
Usually the packing must be without overlaps between goods and other goods or the container walls. The aim is to find the configuration with the maximal density. In some variants the overlapping (of goods with each other and/or with the boundary of the container) is allowed but should be minimized.
| Covering-packing dualities | |
| Covering problems | Packing problems |
|---|---|
| Minimum set cover | Maximum set packing |
| Minimum vertex cover | Maximum matching |
| Minimum edge cover | Maximum independent set |
Read more about Packing Problem: Packing Infinite Space, Related Fields, Packing of Irregular Objects
Famous quotes containing the words packing and/or problem:
“The good husband finds method as efficient in the packing of fire-wood in a shed, or in the harvesting of fruits in the cellar, as in Peninsular campaigns or the files of the Department of State.”
—Ralph Waldo Emerson (1803–1882)
“The problem is simply this: no one can feel like CEO of his or her life in the presence of the people who toilet trained her and spanked him when he was naughty. We may have become Masters of the Universe, accustomed to giving life and taking it away, casually ordering people into battle or out of their jobs . . . and yet we may still dirty our diapers at the sound of our mommy’s whimper or our daddy’s growl.”
—Frank Pittman (20th century)