The Number of Faces in the Integer Hull of Two-Dimensional Asymptotic Programs as a Function of the Determinant.
Abstract
It is shown that, for integer programs whose feasible region derives from a set of inequalities in two variables, the number of faces in the integer hull of the corresponding asymptotic integer program (determined by the linear programming optimum) cannot exceed (in order) the logarithm of the absolute value of the determinant of the asymptotic inequalities. Hence, in this case, the number of faces is logarithmic in the size of the associated group. No results on higher dimensions are given. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1970
- Accession Number
- AD0723098
Entities
People
- Robert G. Jeroslow
Organizations
- Carnegie Mellon University