Caltech Logo

▶︎ CANCELED: H. B. Keller Colloquium

Monday, May 4, 2020
4:00pm to 5:00pm
Add to Cal
Annenberg 105
**CANCELLED** Variations on a theme by George Dantzig: Revisiting the principles of the Simplex Method
Jesus De Loera, Professor of Mathematics, Computer Science and Applied Mathematics, University of California, Davis,

What would happen to optimization without linear programs? Linear programs

(LPs) are the simplest of problems yet, 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. It is often mentioned

as one of the top 10 most influential algorithms of the 20th Century.

But despite its key importance, many simple easy-to-state mathematical

properties of the Simplex method and its geometry remain unknown.

In this talk, I will look at how variations or modifications of the simplex method provide

useful insight into the properties of this popular algorithm. I hope to look into at least

two examples, the first type of abstraction thinks of the problem in a larger combinatorial

topological setting. The second is related to generalizing the pivoting moves used.

This lecture should be accesible to anyone who has heard of optimization.

It is based on work by many people, in particular my joint work with subsets of

Ilan Adler, Steve Klee, Zhenyang Zhang, Laura Sanita, Sean Kafer

KEYWORDS: Linear Optimization, Analysis of Algorithms, geometric techniques in optimization.

For more information, please contact Diana Bohler by phone at 626-395-1768 or by email at [email protected].