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

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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