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)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)