Mathematics Colloquia and Seminars

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.