Variations on a Theme by G. Dantzig: Revisiting the Principles of the Simplex Algorithm

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). Fast algorithms are indispensable.

George Dantzig's Simplex method is one of the most famous algorithms to solve LPs and SIAM even elected it 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. The geometry of the simplex method is a topic in the convex-combinatorial geometry of polyhedra. Perhaps the most famous geometric-combinatorial challenge is to determine a worst-case upper bound for the graph diameter of polyhedra.