We study integer programming instances over polytopes P(A,b)= x:Ax<=b where the constraint matrix A is random, i.e., its entries are i.i.d. Gaussian or, more generally, its rows are i.i.d. from a spherically symmetric distribution. The radius of the largest inscribed ball is closely related to the existence of integer points in the polytope. We show that for m=2^O(sqrt n ), there exist constants c_0 < c_1 such that with high probability, random polytopes are integer feasible if the radius of the largest ball contained in the polytope is at least c_1sqrt log(m n) ; and integer infeasible if the largest ball contained in the polytope is centered at (1 2,...,1 2) and has radius at most c_0sqrt log(m n) . Thus, random polytopes transition from having no integer points to being integer feasible within a constant factor increase in the radius of the largest inscribed ball. We show integer feasibility via a randomized polynomial-time algorithm for finding an integer point in the polytope. Our main tool is a simple new connection between integer feasibility and linear discrepancy. We extend a recent algorithm for finding low-discrepancy solutions (Lovett-Meka, FOCS '12) to give a constructive upper bound on the linear discrepancy of random matrices. By our connection between discrepancy and integer feasibility, this upper bound on linear discrepancy translates to the radius lower bound that guarantees integer feasibility of random polytopes.
Lov ' a sz, Spencer and Vesztergombi @cite_21 showed the following relation between hereditary discrepancy and linear discrepancy.
@cite_21
2080064821
The discrepancy of a set-system is the minimum number d for which the vertices can be 2-coloured red and blue so that in each. of the given sets, the difference between the numbers of red and blue vertices is at most d. In this paper. we introduce various mathematically more tractable variants of this notion. We prove several inequalities relating these numbers, and formulate several further conjectures. We extend the notion to a general matrix, and formulate it as a problem of covering the unit cube by convex bodies.