hirsch conjecture

Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture

  • Edward D. Kim
    • Categories Polyhedra Tags , ,

    We introduce a new combinatorial abstraction for the graphs of polyhedra. The new abstraction is a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of … Read more

    The continuous d-step conjecture for polytopes

  • Antoine Deza
  • Tamás Terlaky
  • Yuriy Zinchenko
    • Categories Linear, Cone and Semidefinite Programming, Polyhedra Tags , , , , ,

    The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension $d$ for … Read more