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 programming problem. Our work is motivated by Kitahara and Mizuno, in which they get upper bounds for the number of different solutions generated by the simplex method.
Citation
Technical paper, Tokyo Institute of Technology
Article
View A Proof by the Simplex Method for the Diameter of a (0,1)-Polytope