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

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