A Polynomial-Time Algorithm for Solving Linear Programs
苏联数学家Khachiyan证明了线性规划可以通过椭球算法的变体在多项式时间内求解，这是理论上的重大突破。
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 SSSR 224 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. Kibernetika 13 94–95. [English translation in Cybernetics 13 94–96.]).