On integer programing with bounded determinants

Abstract

Let $A$ be an $(m\times n)$ integral matrix, and let $P=\{x:Ax\le b\}$ be an $n$-dimensional polytope. The width of $P$ is defined as $w(P)=min\{x\in {\mathbb{Z}}^n\setminus \{0\}:ma{x}_{x\in P}{x}^{\top }u-mi{n}_{x\in P}{x}^{\top }v\}$. Let $\Delta (A)$ and $\delta (A)$ denote the greatest and the smallest absolute values of a determinant among all $r(A)\times r(A)$ sub-matrices of $A$, where $r(A)$ is the rank of a matrix $A$. We prove that if every $r(A)\times r(A)$ sub-matrix of $A$ has a determinant equal to $\pm \Delta (A)$ or $0$ and $w(P)\ge (\Delta (A)-1)(n+1)$, then $P$ contains $n$ affine independent integer points. Also we have similar results for the case of \emph{$k$-modular} matrices. The matrix $A$ is called \emph{totally $k$-modular} if every square sub-matrix of $A$ has a determinant in the set $\{0,\pm k^r:r\in \mathbb{N}\}$. When $P$ is a simplex and $w(P)\ge \delta (A)-1$, we describe a polynomial time algorithm for finding an integer point in $P$. Finally we show that if $A$ is \emph{almost unimodular}, then integer program $\max \{c^{\top }x:x\in P\cap {\mathbb{Z}}^n\}$ can be solved in polynomial time. The matrix $A$ is called \emph{almost unimodular} if $\Delta (A)\le 2$ and any $(r(A)-1)\times (r(A)-1)$ sub-matrix has a determinant from the set $\{0,\pm 1\}$.

The proof of Lemma 4 has been fixed. Some minor corrections has been done

Cited by in corpus (5)

• On $\Delta$-Modular Integer Linear Problems In The Canonical Form And Equivalent Problems
• FPT-algorithms for some problems related to integer programming
• The Width and Integer Optimization on Simplices With Bounded Minors of the Constraint Matrices
• On lattice point counting in $\Delta$-modular polyhedra
• Notes on $\{a,b,c\}$-Modular Matrices