PATHS IN POLYHEDRA. II,
Abstract
The paper is motivated in part by a hypothesis of Saaty (Operations research, 12 (1964), p. 159-161) concerning the paths in polyhedra which are produced by variants of the simplex algorithm. An analysis of his hypothesis and some of its relatives leads to the study of four different types of paths in a polyhedron P and to estimates for the length of each type in terms of the dimension and number of facets of P. Of special interest are the W sub v paths, which never return to a facet from which they have earlier departed. It is conjectured that for an arbitrary nondegenerate linear programming problem and an arbitrary choice of an initial vertex of the feasible region P, there is a sequence of admissible pivots (improving the value of the objective function at each stage) which leads by means of a W sub v path to a critical vertex of P. The conjecture is proved for the case in which P is of dimension three. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1964
- Accession Number
- AD0609498
Entities
People
- Victor Klee
Organizations
- Boeing