A. Paz

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-83-116
August 1983

http://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/6327.html
%F Paz:CSD-83-116