Higher-Dimensional Packing with Order Constraints

Simple item page
dc.creatorFekete, Sandor P.
dc.creatorKoehler, Ekkehard
dc.creatorTeich, Juergen
dc.date2003-08-04
dc.date2005-07-28
dc.date.accessioned2026-07-07T03:20:11Z
dc.date.available2026-07-07T03:20:11Z
dc.descriptionWe 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.
dc.description23 pages, 14 figures, 5 tables, Latex; revision clarifies various minor points, fixes typos, etc. To appear in SIAM Journal on Discrete Mathematics
dc.identifierhttps://arxiv.org/abs/cs/0308006
dc.identifierhttp://arxiv.org/abs/cs/0308006
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31737
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.subjectF.2.2
dc.titleHigher-Dimensional Packing with Order Constraints
dc.typetext

Files

Collections

arXiv