























Consider a class of simplices defined by systems $A x \leq b$ of linear inequalities with $Δ$-modular matrices. A matrix is called $Δ$-modular, if all its rank-order sub-determinants are bounded by $Δ$ in an absolute value. In our work we call a simplex $Δ$-modular, if it can be defined by a system $A x \leq b$ with a $Δ$-modular matrix $A$. And we call a simplex empty, if it contains no points with integer coordinates. In literature, a simplex is called lattice-simplex, if all its vertices have integer coordinates. And a lattice-simplex called empty, if it contains no points with integer coordinates excluding its vertices. Recently, assuming that $Δ$ is fixed, it was shown that the number of $Δ$-modular empty simplices modulo the unimodular equivalence relation is bounded by a polynomial on dimension. We show that the analogous fact holds for the class of $Δ$-modular empty lattice-simplices. As the main result, assuming again that the value of the parameter $Δ$ is fixed, we show that all unimodular equivalence classes of simplices of the both types can be enumerated by a polynomial-time algorithm. As the secondary result, we show the existence of a polynomial-time algorithm for the problem to check the unimodular equivalence relation for a given pair of $Δ$-modular, not necessarily empty, simplices.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。