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:
“He had a wonderful talent for packing thought close, and rendering it portable.”
—Thomas Babington Macaulay (1800–1859)
“Great speeches have always had great soundbites. The problem now is that the young technicians who put together speeches are paying attention only to the soundbite, not to the text as a whole, not realizing that all great soundbites happen by accident, which is to say, all great soundbites are yielded up inevitably, as part of the natural expression of the text. They are part of the tapestry, they aren’t a little flower somebody sewed on.”
—Peggy Noonan (b. 1950)