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.