On Short Combinatorial Walks

Student Commons Building, 4017
Hybrid Hybrid Event

Abstract: The combinatorial diameter of a polyhedron P is a lower bound on the number of iterations required by the simplex method for a linear program on P, and therefore, studies of the diameter have played a crucial role in the effort to determine the worst-case running time of the simplex method. We examine the ... On Short Combinatorial Walks