A Threshold Number for the Shortest Vector Problem in the Infinity Norm

Abstract

For an integer full column rank matrix $A$, we consider the lattice that consists of all integer combinations of columns of $A$. We prove that a shortest non-zero vector $Az$ has infinity norm equal to $1$ whenever the number of columns of $A$ is at least $\Delta$, the largest absolute value of a full rank subdeterminant of $A$. This structural result allows us to design a fixed-parameter tractable algorithm in $\Delta$ for computing a shortest lattice vector in the infinity norm. It also has several applications in integer optimization. In particular, for a polyhedron defined by $Ax\le b$ with integer-valued $b$, an optimal integer solution lies on a face whose dimension is at most $\Delta -1$.

This paper is a continuation of work presented at IPCO 2026