Preprint 05-2020

Proximity bounds for random integer programs

Author(s) : Marcel Celaya , Martin Henk

Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 05-2020

MSC 2000

90C10 Integer programming

52C07 Lattices and convex bodies in $n$ dimensions

Abstract :
We study proximity bounds within a natural model of random integer programs of the type max cx : Ax = b, x >= 0. We prove that (up to a constant depending on the dimension n) the proximity is “generally” bounded by Delta_m(A)^1/(n-m), where is m the rank of A and Delta_m(A) is the maximal absolute value of an m x m subdeterminant of A. This is significantly better than the best deterministic bounds which are linear in Delta_m(A).