
Accession Number : AD0765330
Title : Polytope Pairs and Their Relationship to Linear Programming.
Descriptive Note : Technical rept.,
Corporate Author : WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS
Personal Author(s) : Klee,Victor
Report Date : AUG 1973
Pagination or Media Count : 35
Abstract : An important development in the theory of (convex) polytopes was the determination by Barnette and McMullen of the minimum and maximum of v(P) (number of vertices of P) as P ranges over all simple dpolytopes with n facets. Their results are here extended to certain pairs consisting of a polytope and one of its facets. Corollaries of our main results are the determination of the minimum and maximum of v(P) as P ranges over all simple dpolyhedra with u unbounded and n  u bounded facets, and of the minimum and maximum of v(P not F)/v(F) as (P,F) ranges over all pairs consisting of a simple dpolytope P with n facets and a facet F intersecting all other facets of P. Such pairs, called Kirkman pairs of class (d,n), are related to several aspects of linear programming, including a recent algorithm of Mattheiss for finding all vertices of a polytope defined by a system of linear inequalities. (Author)
Descriptors : (*LINEAR PROGRAMMING, CONVEX SETS), INEQUALITIES, VECTOR SPACES, TOPOLOGY, THEOREMS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE