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):

Report Date:

1973-08-01

Pagination or Media Count:

35.0

Abstract:

An important development in the theory of convex polytopes was the determination by Barnette and McMullen of the minimum and maximum of vP 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 vP as P ranges over all simple d-polyhedra with u unbounded and n - u bounded facets, and of the minimum and maximum of vP not FvF 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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE