A combinatorial characterization of higher-dimensional orthogonal packing

Simple item page
dc.creatorFekete, Sandor P.
dc.creatorSchepers, Joerg
dc.date2003-10-16
dc.date.accessioned2026-07-07T03:20:27Z
dc.date.available2026-07-07T03:20:27Z
dc.descriptionHigher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Previous efforts for exact algorithms have been unable to avoid structural problems that appear for instances in two- or higher-dimensional space. We present a new approach for modeling packings, using a graph-theoretical characterization of feasible packings. Our characterization allows it to deal with classes of packings that share a certain combinatorial structure, instead of having to consider one packing at a time. In addition, we can make use of elegant algorithmic properties of certain classes of graphs. This allows our characterization to be the basis for a successful branch-and-bound framework. This is the first in a series of papers describing new approaches to higher-dimensional packing.
dc.description21 pages, 8 figures, Latex, to appear in Mathematics of Operations Research
dc.identifierhttps://arxiv.org/abs/cs/0310032
dc.identifierhttp://arxiv.org/abs/cs/0310032
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31835
dc.subjectData Structures and Algorithms
dc.subjectComputational Geometry
dc.subjectF.2.2
dc.titleA combinatorial characterization of higher-dimensional orthogonal packing
dc.typetext

Files

Collections

arXiv