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

Abstract

Consider a linear program of the form max{c x : Ax ≤ b}, where A is an m × n integral matrix. In 1986 Cook, Gerards, Schrijver, and Tardos proved that, given an optimal solution x∗, if an optimal integral solution z∗ exists, then it may be chosen such that x∗ − z∗ ∞ < nΔ, where Δ 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Δ can be replaced with n/2 · Δ whenever n ≥ 2 and x∗ is a vertex. We also show that, in certain circumstances, the factor n can be removed entirely