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 d-polytopes 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 d-polyhedra 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 d-polytope 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