Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Face numbers and worst case behavior in linear programmingAlgebra & 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.