2006/04/11 by Sándor P. Fekete, Sandor P. Fekete, Fekete, Sandor P. +4
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Packing Problems #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.cs/0604045
31 pages, 6 figures, 9 tables, to appear in Operations Research; full and updated journal version of sketches that appeared as parts of an extended abstract in ESA'97
arxiv created 2006/04/11 · openalex publication_date 2006/04/11 · 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. Combining the use of our data structure for characterizing feasible packings with our new classes of lower bounds, and other heuristics, we develop a two-level tree search algorithm for solving higher-dimensional packing problems to optimality. Computational results are reported, including optimal solutions for all two--dimensional test problems from recent literature. This is the third in a series of articles describing new approaches to higher-dimensional packing; see cs.DS/0310032 and cs.DS/0402044.