2003/08/04 by Sándor P. Fekete, Sandor P. Fekete, Ekkehard A. Koehler +6
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Manufacturing Process and Optimization #Optimization and Packing Problems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0308006
23 pages, 14 figures, 5 tables, Latex; revision clarifies various minor points, fixes typos, etc. To appear in SIAM Journal on Discrete Mathematics
openalex publication_date 2003/08/04 · arxiv created 2005/07/28 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a first exact study on higher-dimensional packing problems with order constraints. Problems of this type occur naturally in applications such as logistics or computer architecture and can be interpreted as higher-dimensional generalizations of scheduling problems. Using graph-theoretic structures to describe feasible solutions, we develop a novel exact branch-and-bound algorithm. This extends previous work by Fekete and Schepers; a key tool is a new order-theoretic characterization of feasible extensions of a partial order to a given complementarity graph that is tailor-made for use in a branch-and-bound environment. The usefulness of our approach is validated by computational results.