Mathematics Colloquium: Variations on a theme by George B. Dantzig: Revisiting the principles of the simplex method

Speaker: Jesús Deloera, University of California, Davis

Title: Variations on a theme by George B. Dantzig: Revisiting the principles of the simplex method

Abstract: Linear programs (LPs) are, without any doubt, at the core of both the theory and the practice of modern applied and computational Optimization (e.g., in discrete optimization LPs are used in practical computations using branch-and-bound, and in approximation algorithms, e.g., in rounding schemes). George Dantzig's simplex method is one of the most famous algorithms to solve LPs. But despite its key importance, many fundamental questions about the simplex method remain open. In this lecture, I will review some things we still do not know about the simplex method’s performance and I will discuss a simple variation of simplex method that has helped us gain insight about the behavior of pivot rules. This lecture welcomes students and non-experts and it is based in papers joint work with Raymond Hemmecke, Jon Lee, Laura Sanita, & Sean Kafer.

Biographical Sketch: Jesús De Loera's work includes over 90 papers and 2 books in a wide range of topics, including Geometric and Topological Combinatorics, Discrete Geometry, Algorithms, and Combinatorial Optimization. He was elected a fellow of the American Mathematical Society in 2014. In 2019, De Loera a was elected a fellow of the Society of Industrial and Applied Mathematics. For his mentoring and teaching he received the 2013 Chancellor's award for mentoring undergraduate research and, in 2017, the Mathematical Association of America Golden Section teaching Award. He has supervised fourteen Ph.D students, and over 60 undergraduate research projects.

Time: Friday, April 26, 2019, 3:30-4:20 p.m.

Place: Exploratory Hall, Room 4106

Coffee will be served at 3:00 p.m.