Skip to main content


eCommons@Cornell >
College of Engineering >
Operations Research and Information Engineering >
ORIE Technical Reports >

Please use this identifier to cite or link to this item:
Title: The Number of Necessary Constraints in an Integer Program: A New Proof of Scarf's Theorem
Authors: Todd, Michael
Keywords: Scarf's Theorem
Integer Program
Issue Date: Aug-1977
Series/Report no.: 355
Abstract: I give a new proof of Scarf's result that an integer program in n variables has a set of binding constraints of cardinality at most 2n-1.
Appears in Collections:ORIE Technical Reports

Files in This Item:

File Description SizeFormat
Tech report 355.pdf188.21 kBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us