Clearly, the number of extreme points of P cannot be bounded by a polynomial function of m and n . G is the combinatorial diameter, i.e., the maximum length of shortest paths between any two vertices. This argument might be convincing, at least in a passive way, since the geometry of high dimensional objects is not well understood. These questions cannot be answered in our present knowledge even if the dimension is reduced to 4. More striking mystery is the following conjecture posed by W.M. Hirsh in 1957.
P is bounded by m-n , which is obviously a linear function of m and n .
Until now, no one is able to prove or disprove this conjecture. More surprisingly it does not care if the value of the objective function improves, either. The key idea is to solve an LP by solving subproblems. The combinatorial algorithm recursively restricts to a subproblem until it is obviously solved. Unlike the simplex method, the combinatorial algorithm does not suffer from the long-diameter discussion.