A Polynomial-Time Algorithm for Solving Linear Programs

A young Russian mathematician, Leonid G. Khachiyan, has made a stunning theoretical breakthrough (Khachiyan, L. 1979. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR224 1093–1096. [English translation in Soviet Math. Dokl.20 191–194.]) by showing that linear programs can indeed be solved in polynomial time by a variant of an iterative ellipsoidal algorithm developed by N. Z. Shor (Shor, N. 1977. Cut-off method with space extension in convex programming problems. Kibernetika13 94–95. [English translation in Cybernetics13 94–96.]).