A combinatorial characterization of higher-dimensional orthogonal packing

Details A combinatorial characterization of higher-dimensional orthogonal packing A combinatorial characterization of higher-dimensional orthogonal packing

2003-10-16

arxiv.org/abs/cs/0310032v1

Computer Science

Data Structures and Algorithms

21 pages, 8 figures, Latex, to appear in Mathematics of Operations Research

Scientific paper

Higher-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.

Affiliated with

Also associated with

No associations

Rating

A combinatorial characterization of higher-dimensional orthogonal packing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A combinatorial characterization of higher-dimensional orthogonal packing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A combinatorial characterization of higher-dimensional orthogonal packing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-21987