# 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?

• Can't you add trivially true constraints to increase the size of the input?
– joro
Commented Jan 31, 2015 at 11:09
• Why should you want to increase the size of the input? Commented Jan 31, 2015 at 20:42
• To make the input so large so the number of variables is logarithmic and fit your question.
– joro
Commented Feb 1, 2015 at 5:13
• but in the question we already assume that the variables are logarithmic compared to the input size Commented Feb 1, 2015 at 14:05
• I thought about making all instances as yours, but this might exponentially increase the input.
– joro
Commented Feb 2, 2015 at 12:17

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.

1. H.W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8:538–548, 1983.

2. R. Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12:415–440, 1987.

3. Andras Frank and Eva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7:49–65, 1987.

• I think you would need a O(k^p) algorithm for a fixed p, since even a algorithm with 2^O(k) would be exponential? Commented Jan 28, 2015 at 22:27
• Sorry, I used a different notation from the question. By $k$ I mean the number of variables, and $n$ is the size of the input, so a $2^{k}$ algorithm would be polynomial-time if $k=O(\log n)$. Commented Jan 28, 2015 at 23:59
• But suppose you got only binary variables, wouldn't be brute force $2^k$? Commented Jan 29, 2015 at 10:19
• @user3613886, sure, of course, but that's a different problem/question. We weren't promised in the question that the variables are binary.
– D.W.
Commented Jan 30, 2015 at 1:08
• Can't you add trivially true constraints to increase the size of the input?
– joro
Commented Jan 31, 2015 at 11:10