We consider integer programs (IP) defined by equations and box constraints, where it is known that determinants in the constraint matrix are one measure of complexity. For example, Artmann et al. showed that an IP can be solved in strongly polynomial time if the constraint matrix is bimodular, that is, the determinants are bounded in absolute value by two. Determinants are also used to bound the $ell_1$-distance between IP solutions and solutions of its linear relaxation. One of the first works to quantify the complexity of IPs with bounded determinants was that of Heller, who identified the maximum number of differing columns in a totally unimodular constraint matrix. So far, each extension of Hellers bound to general determinants has been exponential in the determinants or the number of equations. We provide the first column bound that is polynomial in both values. As a corollary, we give the first $ell_1$-distance bound that is polynomial in the determinants and the number of equations. We also show a tight bound on the number of differing columns in a bimodular constraint matrix; this is the first tight bound since Hellers result. Our analysis reveals combinatorial properties of bimodular IPs that may be of independent interest, in particular in recognition algorithms for IPs with bounded determinants.
تحميل البحث