<p>I can only give a partial answer to this question. </p>

<p>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.</p>

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

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

CC BY-SA 3.0
2015-01-28T22:27:16.360Z
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?
user3613886
CC BY-SA 3.0
2015-01-28T23:59:32.590Z
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)$.
Michael Lampis
CC BY-SA 3.0
2015-01-29T10:19:03.957Z
But suppose you got only binary variables, wouldn't be brute force $2^k$?
user3613886
CC BY-SA 3.0
2015-01-30T01:08:04.290Z
@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.
CC BY-SA 3.0
2015-01-31T11:10:06.730Z
Can't you add trivially true constraints to increase the size of the input?
joro
CC BY-SA 3.0
2015-01-28T20:38:07.070Z
2015-01-28T20:38:07.070Z
Michael Lampis
<p>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?</p>

CC BY-SA 3.0
2015-01-31T11:09:35.970Z
Can't you add trivially true constraints to increase the size of the input?
joro
CC BY-SA 3.0
2015-01-31T20:42:43.443Z
Why should you want to increase the size of the input?
user3613886
CC BY-SA 3.0
2015-02-01T05:13:48.703Z
To make the input so large so the number of variables is logarithmic and fit your question.
joro
CC BY-SA 3.0
2015-02-01T14:05:35.737Z
but in the question we already assume that the variables are logarithmic compared to the input size
user3613886
CC BY-SA 3.0
2015-02-02T12:17:21.137Z
I thought about making all instances as yours, but this might exponentially increase the input.
joro
<cc.complexity-theory><np><open-problem>
Integer linear programming in logarithmic number of variables
user3613886
# Integer linear programming in logarithmic number of variables

(Asked by: username_0 on 2015-01-28)

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?

**Tags:** cc.complexity-theory, np, open-problem

> **Comments:**
> **username_1**: Can't you add trivially true constraints to increase the size of the input?  
> **username_0**: Why should you want to increase the size of the input?  
> **username_1**: To make the input so large so the number of variables is logarithmic and fit your question.  
> **username_0**: but in the question we already assume that the variables are logarithmic compared to the input size  
> **username_1**: I thought about making all instances as yours, but this might exponentially increase the input.  

---

## 1 answers

### Answer by username_2 on 2015-01-28. Score: 15

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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)$.  
> **username_0**: But suppose you got only binary variables, wouldn't be brute force $2^k$?  
> **username_3**: @username_0, sure, of course, but that's a different problem/question.  We weren't promised in the question that the variables are binary.  
> **username_1**: Can't you add trivially true constraints to increase the size of the input?  

---

