▶︎ 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.