A Discrepancy based Approach to Integer Programming

ACO Student Seminar
Friday, February 24, 2012 - 1:00pm
1 hour (actually 50 minutes)
Klaus 1116W
CoC, Georgia Tech
I will show a new approach based on the discrepancy of the constraint matrix to verify integer feasibility of polytopes. I will then use this method to show a threshold phenomenon for integer feasibility of random polytopes. The random polytope model that we consider is P(n,m,x0,R) - these are polytopes in n-dimensional space specified by m "random" tangential hyperplanes to a ball of radius R centered around the point x0. We show that there exist constants c_1 < c_2 such that with high probability, the random polytope P(n,m,x0=(0.5,...,0.5),R) is integer infeasible if R is less than c_1sqrt(log(2m/n)) and the random polytope P(n,m,x0,R) is integer feasible for every center x0 if the radius R is at least c_2sqrt(log(2m/n)). Thus, a transition from infeasibility to feasibility happens within a constant factor increase in the radius. Moreover, if the polytope contains a ball of radius Omega(log (2m/n)), then we can find an integer solution with high probability (over the input) in randomized polynomial time. This is joint work with Santosh Vempala.