A. Paz

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-83-116

, 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},
    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