Return to Colloquia & Seminar listing
Face numbers and worst case behavior in linear programming
Algebra & Discrete Mathematics| Speaker: | Nicholas Nguyen, UC Davis |
| Location: | 1147 MSB |
| Start time: | Thu, Mar 9 2006, 12:10PM |
In order to examine the behavior of a linear optimization algorithm like the simplex method, one can look at the face numbers of the polytope defined by the linear constraints.
A polytope with many vertices, for example, can take a long time to solve. In 1957, Motzkin claimed that given n facets in d dimensions, the largest possible number of vertices on a polytope can be found on the cyclic polytope with n facets. This claim was later proved in 1970 by McMullen and became the upper bound theorem.
In this talk, I will introduce the upper bound theorem in the context of linear programming and give a recent proof by Gil Kalai. Next, I will introduce a related problem stated by Klee in 1965 that is very relevant to the behavior and performance of the simplex method along with some recent work on this problem.