March Notices

The March Notices of the AMS features a retrospective on George Dantzig, who died in 2005, and a description of his simplex method to solve linear programming problems.

Linear programming is the solution of constrained optimization problems with linear objective function and linear constraints. Since the set of allowable input values is a convex polytope, the solution must (usually) be one of the vertices of the polytope. One sure-fire method for finding the solution is to try every vertex. For small problems this is an eminently practical procedure, but for large problems this takes time exponential in the number of vertices. The simplex method is the first algorithm that in practice efficiently solves linear programming problems by only trying a subset of the vertices. In the worst case, the simplex algorithm can still visit every vertex, but for the vast majority of practical problems the algorithm only takes polynomial time. (There are more recent algorithms that have better worst-case performance. I have a upcoming post planned on the subject.)

This month’s What is… is János Kollár on What is… a minimal model. Minimal models are the current target of research in birational algebraic geometry — the current hope is that most (for a well-defined meaning of most) birational equivalence classes of algebraic varieties have a minimal model. Minimal models are not unique, but two birationally equivalent minimal models are closely related. Most introductions to the subject I have seen take an algebraic approach. Kollár instead answers the question in complex analytic terms.

(I had more for this post, but WordPress just ate it. More later.)