Proximity Bounds for Random Integer Programs

Abstract

We study proximity bounds within a natural model of random integer programs of the type maxc⊤x:Ax=b,x∈Z≥0, where A∈ Zm×n is of rank m, b∈ Zm and c∈ Zn. In particular, we seek bounds for proximity in terms of the parameter Δ(A), which is the square root of the determinant of the Gram matrix AA⊤ of A. We prove that, up to constants depending on n and m, the proximity is “generally” bounded by Δ(A) 1/(n-m), which is significantly better than the best deterministic bounds which are, again up to dimension constants, linear in Δ(A). © 2021, Springer Nature Switzerland AG.