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