I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes arguments of Khaichayan and Von zur Gathen and Sieveking). However I understand from the line '..we indicate an algorithm for the solution of this problem that is polynomial for any fixed value of $n$, the number of integer variables' that the complexity is polynomial if number of integer variables is fixed. I am interested in complexity with fixed number of integer variables and polynomial number of real variables.

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$?

  1. 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 interested in case of $n_1$ is fixed and $n_2=O(L^c)$.

  1. Is there a down to earth explanation of what Lenstra is doing?

  2. What is the space requirement?

  3. What is a good reference for this type of mixed integer linear program?


Your Answer

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

Browse other questions tagged or ask your own question.