
Accession Number : AD0609498
Title : PATHS IN POLYHEDRA. II,
Corporate Author : BOEING SCIENTIFIC RESEARCH LABS SEATTLE WASH
Personal Author(s) : Klee,Victor
Report Date : OCT 1964
Pagination or Media Count : 31
Abstract : The paper is motivated in part by a hypothesis of Saaty (Operations research, 12 (1964), p. 159161) 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)
Descriptors : (*GEOMETRIC FORMS, LINEAR PROGRAMMING), (*LINEAR PROGRAMMING, GEOMETRIC FORMS), OPERATIONS RESEARCH, ITERATIONS
Distribution Statement : APPROVED FOR PUBLIC RELEASE