Integer linear programming in logarithmic number of variables I read that integer linear programming is solvable in polynominal time if the number $n$ of variables is fixed, i.e. $n \in O(1)$. If the number of variables grows logarithmically, i.e. $n \in O(\log_2(N))$ for a given input of size $N$, is the problem still solvable in polynominal time or is this an open problem?
I can only give a partial answer to this question. 

A result by Lenstra (later improved by Kannan, and Frank and Tardos) states that ILP with $k$ variables can be solved in time $k^{O(k)}$ (times a polynomial in the size of the ILP). Therefore, ILP is in P when the number of variables is $O(\log n/\log\log n)$. I am not sure if a $2^{O(k)}$ algorithm is known, or if such an algorithm would contradict the ETH.

I found this information in Daniel Lokshtanov's dissertation. Here are the relevant references.


H.W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8:538–548, 1983.
R. Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12:415–440, 1987.
Andras Frank and Eva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7:49–65, 1987.