2003/10/16 by Sándor P. Fekete, Sandor P. Fekete, Fekete, Sandor P. +2
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Packing Problems #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0310032
21 pages, 8 figures, Latex, to appear in Mathematics of Operations Research
arxiv created 2003/10/16 · openalex publication_date 2003/10/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.