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

1983

This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/Archive/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