1)-polytope

A Proof by the Simplex Method for the Diameter of a (0,1)-Polytope

  • Tomonari Kitahara
  • Shinji Mizuno
    • Categories Graphs and Matroids, Linear Programming Tags , , , ,

    Naddef shows that the Hirsch conjecture is true for (0,1)-polytopes by proving that the diameter of any $(0,1)$-polytope in $d$-dimensional Euclidean space is at most $d$. In this short paper, we give a simple proof for the diameter. The proof is based on the number of solutions generated by the simplex method for a linear … Read more