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 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

Download

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