Abstract
Warren M. Hirsch posed the conjecture which bears his name in a letter of 1957 to George B. Dantzig. Simply stated in geometric terms, Hirsch proposed that a polytope in dimension d with n facets admits a path of at most (n–d) edges connecting any two vertices. Hirsch posed his conjecture in the context of a linear program in d variables and n constraints as requiring a maximum of (n–d) pivots — steps of the simplex algorithm — on the shortest path, to achieve an optimum. Over the years the Hirsch conjecture has attracted much research attention, and has been proved in a number of special cases. This article contributes a proof in the general bounded case.