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?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Can't you add trivially true constraints to increase the size of the input? $\endgroup$– joroJan 31, 2015 at 11:09
-
$\begingroup$ Why should you want to increase the size of the input? $\endgroup$– user3613886Jan 31, 2015 at 20:42
-
$\begingroup$ To make the input so large so the number of variables is logarithmic and fit your question. $\endgroup$– joroFeb 1, 2015 at 5:13
-
$\begingroup$ but in the question we already assume that the variables are logarithmic compared to the input size $\endgroup$– user3613886Feb 1, 2015 at 14:05
-
$\begingroup$ I thought about making all instances as yours, but this might exponentially increase the input. $\endgroup$– joroFeb 2, 2015 at 12:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
$\begingroup$ 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? $\endgroup$ Jan 28, 2015 at 22:27
-
$\begingroup$ 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)$. $\endgroup$ Jan 28, 2015 at 23:59
-
$\begingroup$ But suppose you got only binary variables, wouldn't be brute force $2^k$? $\endgroup$ Jan 29, 2015 at 10:19
-
$\begingroup$ @user3613886, sure, of course, but that's a different problem/question. We weren't promised in the question that the variables are binary. $\endgroup$– D.W.Jan 30, 2015 at 1:08
-
$\begingroup$ Can't you add trivially true constraints to increase the size of the input? $\endgroup$– joroJan 31, 2015 at 11:10