A Note on Non-Degenerate Integer Programs with Small Sub-Determinants

Abstract

The intention of this note is two-fold. First, we study integer optimization problems in standard form defined by $A\in {\mathbb{Z}}^{m\times n}$ and present an algorithm to solve such problems in polynomial-time provided that both the largest absolute value of an entry in $A$ and $m$ are constant. Then, this is applied to solve integer programs in inequality form in polynomial-time, where the absolute values of all maximal sub-determinants of $A$ lie between $1$ and a constant.