9 papers
Lifts for Voronoi cells of lattices
Matthias Schymura, Ina Seidel, Stefan Weltge
Many polytopes arising in polyhedral combinatorics are linear projections of higher-dimensional polytopes with significantly fewer facets. Such lifts may yield compressed represent…
Computational Aspects of Relaxation Complexity: Possibilities and Limitations
Gennadiy Averkov, Christopher Hojny, Matthias Schymura
The relaxation complexity of the set of integer points contained in a polyhedron is the smallest number of facets of any polyhedron such that the integer p…
Packing minima and lattice points in convex bodies
Martin Henk, Matthias Schymura, Fei Xue
Motivated by long-standing conjectures on the discretization of classical inequalities in the Geometry of Numbers, we investigate a new set of parameters, which we call \emph{packi…
Complexity of linear relaxations in integer programming
Gennadiy Averkov, Matthias Schymura
For a set of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with is called the relaxation complexity…
Tropical Ehrhart Theory and Tropical Volume
Georg Loho, Matthias Schymura
We introduce a novel intrinsic volume concept in tropical geometry. This is achieved by developing the foundations of a tropical analog of lattice point counting in polytopes. We e…
On compact representations of Voronoi cells of lattices
Christoph Hunkenschröder, Gina Reuland, Matthias Schymura
In a seminal work, Micciancio & Voulgaris (2013) described a deterministic single-exponential time algorithm for the Closest Vector Problem (CVP) on lattices. It is based on the co…