Papers for

integer programming software developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Upper bound found for edges in Gomory corner polyhedron geometry

An upper bound on the number of edges of a Gomory corner polyhedron

Abstract: We establish the first nontrivial upper bound on the number of edges of a Gomory corner polyhedron, resolving a long-standing open question. For an $n$-dimensional corner polyhedron associated with an integer lattice of determinant $δ$, the number of edges is at most $$ O\left(n6^n \cdot \bigl(1+\log_2(2δ)\bigr)^{2n-3}\right). $$ This improves the standard bound obtained by counting pairs of vertices, reducing the logarithmic exponent from $(2n-2)$ to $(2n-3)$.

Thu 12 NovComputational GeometryDiscrete Mathematics
The gist
Counting the edges in a special kind of geometric shape called a Gomory corner polyhedron has been a challenging problem for many years. The paper shows a new way to put an upper limit on how many edges these shapes can have, depending on their dimension and other properties. This new bound is tighter than previously known results. The authors thus resolved a question that people in math and computer science had been stuck on for some time.
Open → 2611.16839v1