$\begingroup$
$\endgroup$
2
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?
mhum
3,4521 gold badge23 silver badges22 bronze badges
-
$\begingroup$ What does $O^*$ mean? See also this answer to a related question. $\endgroup$Jeffε– Jeffε2013年03月22日 18:16:32 +00:00Commented Mar 22, 2013 at 18:16
-
3$\begingroup$ The $O^*$ notation usually ignores polynomial factors in the instance size. $\endgroup$Serge Gaspers– Serge Gaspers2013年03月22日 22:10:10 +00:00Commented Mar 22, 2013 at 22:10
1 Answer 1
$\begingroup$
$\endgroup$
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.
answered Mar 22, 2013 at 22:07
Serge Gaspers
5,20633 silver badges43 bronze badges