# A Simplified Version of H. W. Lenstra's Integer Programming Algorithm and Some Applications

### A. Paz

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-83-116

August 1983

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-116.pdf

A very interesting algorithm has been recently suggested by H. W. Lenstra, Jr. [1] for solving integer programming problems. One part of that algorithm was further improved in [2]. The algorithm was shown to be polynomial in the length of the input, for a fixed number of variables. On the other hand the algorithm is impractical for a large number of variables and its implementation is not clear even for a small number of variables. We suggest here a few simplifications and improvements to that algorithm, making its implementation easy (though still impractical for a great number of variables). As a byproduct we show how to solve diophantine linear equations over the nonnegative integers. For a small number of variables (3 or 4) a practical and fast algorithm for solving such equation results.

BibTeX citation:

@techreport{Paz:CSD-83-116, Author = {Paz, A.}, Title = {A Simplified Version of H. W. Lenstra's Integer Programming Algorithm and Some Applications}, Institution = {EECS Department, University of California, Berkeley}, Year = {1983}, Month = {Aug}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6327.html}, Number = {UCB/CSD-83-116}, Abstract = {A very interesting algorithm has been recently suggested by H. W. Lenstra, Jr. [1] for solving integer programming problems. One part of that algorithm was further improved in [2]. The algorithm was shown to be polynomial in the length of the input, for a fixed number of variables. On the other hand the algorithm is impractical for a large number of variables and its implementation is not clear even for a small number of variables. We suggest here a few simplifications and improvements to that algorithm, making its implementation easy (though still impractical for a great number of variables). As a byproduct we show how to solve diophantine linear equations over the nonnegative integers. For a small number of variables (3 or 4) a practical and fast algorithm for solving such equation results.} }

EndNote citation:

%0 Report %A Paz, A. %T A Simplified Version of H. W. Lenstra's Integer Programming Algorithm and Some Applications %I EECS Department, University of California, Berkeley %D 1983 %@ UCB/CSD-83-116 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6327.html %F Paz:CSD-83-116