On the Complexity of Integer Programming

Author(s)
Papadimitriou, Christos H.
Thumbnail
DownloadMIT-LCS-TM-152.pdf (1.339Mb)
Metadata
Show full item record
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.
Date issued
1980-02
URI
https://hdl.handle.net/1721.1/148979
Series/Report no.
MIT-LCS-TM-152
Collections