Linear programming is arguably the greatest success story in the field of optimization. A linear program is a mathematical model of an optimization problem that can be represented by linear relationships. For example, the classical diet problem asks how to combine the cheapest diet from a given list of groceries while meeting the recommended dietary guidelines. Geometrically, a linear program defines a high-dimensional polyhedron, for instance a deformed cube, and the objective is to find the corner that is furthest in a given direction.

The use of linear programming dates back to World War Two, and the first practical algorithm for solving linear programs, the simplex algorithm, was published by George B. Dantzig in 1947. An extensive effort has since then advanced the theoretical understanding and practical use of linear programming. For instance, the development of better linear programming algorithms outperformed the development of new hardware throughout the 1990s.

In this talk I give a basic introduction to linear programming, its history, and the status of some important unanswered questions. I also present some of my own results, focusing mainly on recent joint work with Uri Zwick in which we introduce and upper bound the performance of an improved variant of the Random-Facet simplex algorithm by Kalai (1992) and Matousek, Sharir, and Welzl (1992); the best known combinatorial algorithm for linear programming.