Maximal lattice free bodies, test sets and the Frobenius problem

Simple item page
dc.creatorJensen, Anders
dc.creatorLauritzen, Niels
dc.creatorRoune, Bjarke
dc.date2007-05-30
dc.date2007-05-30
dc.date.accessioned2026-07-07T08:09:25Z
dc.date.available2026-07-07T08:09:25Z
dc.descriptionMaximal lattice free bodies are maximal polytopes without interior integral points. Scarf initiated the study of maximal lattice free bodies relative to the facet normals in a fixed matrix. In this paper we give an efficient algorithm for computing the maximal lattice free bodies of an integral matrix A. An important ingredient is a test set for a certain integer program associated with A. This test set may be computed using algebraic methods. As an application we generalize the Scarf-Shallcross algorithm for the three-dimensional Frobenius problem to arbitrary dimension. In this context our method is inspired by the novel algorithm by Einstein, Lichtblau, Strzebonski and Wagon and the Groebner basis approach by Roune.
dc.identifierhttps://arxiv.org/abs/0705.4439
dc.identifierhttp://arxiv.org/abs/0705.4439
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/131536
dc.subjectCombinatorics
dc.subjectOptimization and Control
dc.titleMaximal lattice free bodies, test sets and the Frobenius problem
dc.typetext

Files

Collections

arXiv