We are experiencing some difficulties with our submission forms, which we are working to resolve. If you have any issues, please contact us at dspace-lib@mit.edu.
On the Complexity of Integer Programming
Name
MIT-LCS-TM-152.pdf
Size
1.34 MB
Format
Adobe PDF
Checksum
(MD5)
efe12162fe63bda45277f653377e37cd
Author(s)
Papadimitriou, Christos H.
Date Issued
February 1980
Series/Report no.
MIT-LCS-TM-152
Abstract
We give a simple proof that integer programming is in NP. Our proof also establishes that there is a pseudopolynomial time algorithm for integer programming with any (fixed) number of constraints.
Persistent DSpace Link