Thresholds in random integer programs

Karthik Chandrasekaran gave a talk at TTI today on the feasibility of integer programs. Given a polytope defined by the inequalities $A x \le b$ in dimension $n$, can we say whether the polytope contains an integer point? In general, the problem is NP-hard, but efficient algorithms are known for special sub-cases. The goal in this talk was to understand if random instances of the problem are also hard.

The first thing to figure out is what do we mean by a random instance? Consider a point $x_0$ and the sphere $S$ of radius $R$ around $x_0$. Now draw $m$ vectors $x_1, x_2, \ldots, x_m$ uniformly from the surface of the unit sphere, and consider the polytope defined by faces which are tangent to $S$ at $x_0 + x_i$ for $i = 1, 2, \ldots, m$. That is, the vector $x_0 + x_i$ is the normal vector of that face. This defines a random polytope whose distribution depends on the parameters $(n,m,x_0,R)$. The goal is to find how $R$ scales with $n$ and $m$ such that with high probability, the polytope contains an integer point for all $x_0$.

If the radius $R$ is too small, then this will be hard to do because guaranteeing that an integer point is in the interior for all $x_0$ becomes hard. If $R = \sqrt{n}/2$, then we will always have an integer point. What should the real scaling for $R$ look like?

The simple form of the main result is that if $n \le m \le 2^{\sqrt{n}}$ and $R \ge c_1 \sqrt{log(m/n)}$, with high probability the polytope will have an integer point for every $x_0$. Conversely, if $R \le c_0 \sqrt{ log(m/n) }$, then with high probability the polytope “centered” at $x_0 = (1/2,1/2,\ldots,1/2)$ with not contain an integer point. Note that if the number of faces is linear in $n$, then a constant radius is sufficient. I’m trying to square that with the “infinite dimensional spheres have vanishing volume and expanding surface area” but I think the fact that the polytope is “pointy” means that $L_1$ geometry gives better intuition.

To prove these bounds on $R$, they make a connection to the discrepancy of random Gaussian matrices (which approximate the random unit vector row matrices). The paper is on arxiv for those who want to take a look.

This site uses Akismet to reduce spam. Learn how your comment data is processed.