Upper bound found for edges in Gomory corner polyhedron geometry
An upper bound on the number of edges of a Gomory corner polyhedron
Computational GeometryDiscrete Mathematics
Summary
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.
What this means in practice
- •For optimization algorithm designers: Refine complexity estimates for algorithms using Gomory corner polyhedra by leveraging new tighter edge count bounds.
- •For integer programming software developers: Improve heuristics and stopping criteria by incorporating tighter theoretical limits on Gomory polyhedron structure.
A theory result. No direct application yet.
Authors
A. Yu. Chirkov, S. I. Veselov, D. V. Gribanov, D. S. Malyshev, N. Yu. Zolotykh
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)$.