Mahidol University International College
16:00 Wednesday, 28 June 2017, Room 3306, MUIC
In the spring of 1979, Soviet mathematician Leonid Khachiyan published a polynomial time algorithm for linear programming, the first of its kind. Despite the fact that it was ultimately less practical than the popular simplex method, it was still considered to be a theoretical breakthrough that inspired a whole slew of algorithms for a more general class of problems. Khachiyan's (ellipsoid) algorithm was drastically different from previous methods in that it exploited less of the combinatorial nature of the problem.
The plan is for this talk to be the first in a short series on the history and development of optimization algorithms for linear programming, starting with the simplex method (this talk) and ending with the ellipsoid method (future talk) with derivations and generalizations along the way. We will motivate the series by introducing a game theoretical application for linear programming.