Improving the Cook et al. Proximity Bound Given Integral Valued Constraints

Abstract

Consider a linear program of the form $\max c^{\top }x:Ax\le b$, where $A$ is an $m\times n$ integral matrix. In 1986 Cook, Gerards, Schrijver, and Tardos proved that, given an optimal solution $x^{\ast }$, if an optimal integral solution $z^{\ast }$ exists, then it may be chosen such that ${\Vert x^{\ast }-z^{\ast }\Vert }_{\infty }<n\Delta$, where $\Delta$ is the largest magnitude of any subdeterminant of $A$. Since then an open question has been to improve this bound, assuming that $b$ is integral valued too. In this manuscript we show that $n\Delta$ can be replaced with $\frac{n}{2}\cdot \Delta$ whenever $n\ge 2$. We also show that, in certain circumstances, the factor $n$ can be removed entirely.

13 pages