The Number of Necessary Constraints in an Integer Program: A New Proof of Scarf's Theorem
Permanent Link(s)
Collections
Author
Todd, Michael
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.
Journal / Series
355
Date Issued
1977-08
Keywords
Type
technical report