2
$\begingroup$

It is well-known that Lenstra's famous algorithm (presented in the paper Integer programming with a fixed number of variables) can solve an ILP problem in $O^*(f(k))$ time where k is the number of variables occur in the ILP.

My question is that whether the algorithm or any of its improved versions can output all feasible solutions in $O^*(f(k))$ time?

|cite|improve this question
$\endgroup$
  • $\begingroup$ What does $O^*$ mean? See also this answer to a related question. $\endgroup$ – Jeffε Mar 22 '13 at 18:16
  • 3
    $\begingroup$ The $O^*$ notation usually ignores polynomial factors in the instance size. $\endgroup$ – Serge Gaspers Mar 22 '13 at 22:10
6
$\begingroup$

No. The number of feasible solutions cannot be upper bounded by $f(k)n^{O(1)}$.

Consider the integer program $I_n: 1 \le x\le 2^n$ with the integer variable $x$. So, $k=1$ and the program can be described with $O(n)$ bits. But it has $2^n$ solutions, which is exponential in the instance size.

|cite|improve this answer
$\endgroup$

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.