Thursday, 11:30 - 11:55 h, Room: H 2036


Tomonari Kitahara
A proof by the simplex method for the diameter of a (0,1)-polytope

Coauthor: Shinji Mizuno


Naddef (1989) showed 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 (2011), in which they got upper bounds for the number of different solutions
generated by the simplex method.


Talk 3 of the contributed session Thu.1.H 2036
"Linear programming: Theory and algorithms" [...]
Cluster 4
"Conic programming" [...]


  To apply for Payday Loans In United States you don't have to seek the help of relatives or go to a bank. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.