Monday, December 4, 2017

12:15–13:10

Schreiber 006

12:15–13:10

Schreiber 006

:: MINT Distinguished Lecture ::

Gil Kalai

The Hebrew University of Jerusalem

The combinatorics of convex polytopes and the simplex algorithm for linear programming

Linear programming is the problem of maximizing a linear function subject to a system of linear inequalities. The set of solutions for the linear inequalities is a convex polytope *P* (which can be unbounded). The simplex algorithm was developed by George Danzig. Geometrically it can be described by moving from one vertex to a neighboring vertex as to improve that value of the objective function. The precise rule for choosing the next vertex is called the "pivot rule".

The simplex algorithm is one of the most successful mathematical algorithms. Understanding this success is an applied question, it is a vaguely stated, and it connects with computers. The problem has strong relations to the study of convex polytopes that mathematicians found fascinating from ancient times and was my own starting point.

After a brief overview of the history of the subject I will concentrate on diameter of graphs of polytopes and on randomized pivot rules.