▶︎ CANCELED: H. B. Keller Colloquium

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.