On lattice point counting in $\Delta$-modular polyhedra

Abstract

Let a polyhedron $P$ be defined by one of the following ways: (i) $P=\{x\in R^n:Ax\le b\}$, where $A\in Z^{(n+k)\times n}$, $b\in Z^{(n+k)}$ and $rankA=n$; (ii) $P=\{x\in R_{+}^n:Ax=b\}$, where $A\in Z^{k\times n}$, $b\in Z^k$ and $rankA=k$. And let all rank order minors of $A$ be bounded by $\Delta$ in absolute values. We show that the short rational generating function for the power series $$\sum _{m\in P\cap Z^n}{x}^m$$ can be computed with the arithmetic complexity $O\left(T_{SNF}(d)\cdot d^k\cdot d^{{\log }_2\Delta }\right),$ where $k$ and $\Delta$ are fixed, $d=\dim P$, and $T_{SNF}(m)$ is the complexity to compute the Smith Normal Form for $m\times m$ integer matrix. In particular, $d=n$ for the case (i) and $d=n-k$ for the case (ii). The simplest examples of polyhedra that meet conditions (i) or (ii) are the simplicies, the subset sum polytope and the knapsack or multidimensional knapsack polytopes. We apply these results to parametric polytopes, and show that the step polynomial representation of the function $c_P(y)=|P_y\cap Z^n|$, where $P_y$ is parametric polytope, can be computed by a polynomial time even in varying dimension if $P_y$ has a close structure to the cases (i) or (ii). As another consequence, we show that the coefficients $e_i(P,m)$ of the Ehrhart quasi-polynomial $$\left|mP\cap Z^n\right|=\sum _{j=0}^n{e}_i(P,m)m^j$$ can be computed by a polynomial time algorithm for fixed $k$ and $\Delta$.

References in corpus (7)

• Counting with rational generating functions
• Intermediate Sums on Polyhedra: Computation and Real Ehrhart Theory
• On integer programing with bounded determinants
• On the complexity of quasiconvex integer minimization problem
• The Width and Integer Optimization on Simplices With Bounded Minors of the Constraint Matrices
• FPT-algorithms for some problems related to integer programming
• On Integer Programming, Discrepancy, and Convolution

Cited by in corpus (1)

• On $\Delta$-Modular Integer Linear Problems In The Canonical Form And Equivalent Problems