16
$\begingroup$

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?

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

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.

$\endgroup$
  • $\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$ – user3613886 Jan 28 '15 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$ – Michael Lampis Jan 28 '15 at 23:59
  • $\begingroup$ But suppose you got only binary variables, wouldn't be brute force $2^k$? $\endgroup$ – user3613886 Jan 29 '15 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 '15 at 1:08
  • $\begingroup$ Can't you add trivially true constraints to increase the size of the input? $\endgroup$ – joro Jan 31 '15 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.