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?
Asked
Active
Viewed 604 times
16
-
Can't you add trivially true constraints to increase the size of the input? – joro Jan 31 '15 at 11:09
-
Why should you want to increase the size of the input? – user3613886 Jan 31 '15 at 20:42
-
To make the input so large so the number of variables is logarithmic and fit your question. – joro Feb 01 '15 at 05:13
-
but in the question we already assume that the variables are logarithmic compared to the input size – user3613886 Feb 01 '15 at 14:05
-
I thought about making all instances as yours, but this might exponentially increase the input. – joro Feb 02 '15 at 12:17
1 Answers
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.
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.
Michael Lampis
- 3,698
- 22
- 31
-
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 Jan 28 '15 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)$. – Michael Lampis Jan 28 '15 at 23:59
-
But suppose you got only binary variables, wouldn't be brute force $2^k$? – user3613886 Jan 29 '15 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. Jan 30 '15 at 01:08
-
Can't you add trivially true constraints to increase the size of the input? – joro Jan 31 '15 at 11:10