Skip to main content
1 of 6
Turbo
  • 13.3k
  • 1
  • 20
  • 70

Fixed parameter mixed integer linear program complexity

Suppose we have $A\in\Bbb Z^{m\times(n_1+n_2)}$ and $B\in\Bbb Z^m$ and asked to find $X\in\Bbb Z^{n_1}\times \Bbb R^{n_2}$ in $AX\leq B$ then what is the complexity with with which we can find $X$?

Can we find $X$ in $O(n_1^{cn_1}((n_2+1)m)^cL)$ arithmetic operations on $O(L^c)$ bit words where non-negative $c$ is fixed and $L$ is number of bits needed in any entry of $A$ or $B$?

The above scaling is consistent with case $n_1=0$ (Real Linear Programming) or $n_2=0$ (Integer Linear Programming).

I am mostly interested in case of $n_1$ is fixed and $n_2=O(L^c)$.

Turbo
  • 13.3k
  • 1
  • 20
  • 70