A CONSTRUCTIVE INDUCTIVE PROOF OF THE HIRSCH CONJECTURE
作者： Paul C. Kettler
DOI:
关键词: Bounded function 、 Linear programming 、 Path (graph theory) 、 Context (language use) 、 Simplex algorithm 、 Mathematics 、 Conjecture 、 Constructive proof 、 Combinatorics 、 Hirsch conjecture
摘要: Warren M. Hirsch posed the conjecture which bears his name in a letter of 1957 to George B. Dantzig. Simply stated geometric terms, proposed that polytope dimension dwith n facets admits path at most (n−d) edges connecting any two vertices. context linear program d variables and constraints as requiring maximum (n− d) pivots — steps simplex algorithm— on shortest path, achieve an optimum. Over years theHirsch has attractedmuch research attention, been proved number special cases. This article contributes proof general bounded case.
参考文章(55)
Jr. Marshall Hall, Combinatorial theory (2nd ed.) John Wiley & Sons, Inc.. ,(1998)
M. L. Balinski, On two special classes of transportation polytopes Pivoting and Extension. pp. 43- 58 ,(1974) , 10.1007/BFB0121240
Ilan Adler, George Dantzig, Katta Murty, Existence of A-avoiding paths in abstract polytopes Pivoting and Extension. pp. 41- 42 ,(1974) , 10.1007/BFB0121239
W. T. Tutte, Introduction to the theory of matroids ,(1971)
Victor Klee, Adjoints of projective transformations and face-figures of convex polytopes Mathematical Programming Studies. pp. 208- 216 ,(1978) , 10.1007/BFB0121203
Victor Klee, Christoph Witzgall, FACETS AND VERTICES OF TRANSPORTATION POLYTOPES ,(1967)
Christoph Witzgall, Josef Stoer, Convexity and Optimization in Finite Dimensions I ,(1970)
Robin Milner, Mathematical Centre Tracts Mathematisch Centrum. ,(1976)
George J. Minty, Victor Klee, HOW GOOD IS THE SIMPLEX ALGORITHM Inequalities. pp. 159- 175 ,(1970)
Ilan Adler, George B. Dantzig, Maximum diameter of abstract polytopes Pivoting and Extension. pp. 20- 40 ,(1974) , 10.1007/BFB0121238