Skip to main content
5 of 6
added 268 characters in body; edited title
Turbo
  • 13.3k
  • 1
  • 20
  • 70

What exactly did Lenstra prove on mixed integer linear program?

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. Is the space requirement polynomial (for integer programming it is infact linear and does not depend on number of variables $n_1$ when $n_2=0$)?

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

Turbo
  • 13.3k
  • 1
  • 20
  • 70