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

Marcel Celaya, Stefan Kuhlmann, Joseph Paat +1

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 op…