Fixed dimension integer programming (both Lenstra's and Barvinok's) uses LLL which guarantees short vectors but not the shortest possible.

Suppose for a given integer programming problem find $x\in\Bbb Z^n$ on condition $Ax\leq b$ where $A\in\Bbb Z^{m\times n}$ and $b\in\Bbb Z^m$ holds we have that the LLL returns optimal basis in polynomial time then are there conditions under which the complexity of the integer programming problem go down from $O(mLn^n)$ to $O(poly(mL)n^{n^\alpha})$ where $L$ is total word size in bits in the presentation of the program at a fixed $\alpha\in[0,1)$?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.