Known for his Ellipsoid Algorithm for linear programming, Khachiyan proved the existence of an efficient way to solve linear programming problems thought to be intractable until that time. His 1979 breakthrough dealt with the underlying mathematics, opening doors beyond linear programming to what is known as combinatorial optimization—finding the best of a finite, but often astronomically large, number of options.
Khachiyan's 1979 Doklady paper was but his fourth in a long list of single and co-authored publications in diverse areas of algorithms, computational complexity, and applications. These included cyclic games on graphs with applications to artificial intelligence; matching; nonlinear programming; extremal covering and inscribed ellipsoids and rounding of polytopes; matrix scaling; complexity of semidefinite programming; interior point methods for structured linear programming; fast approximations for matrix games, for large-scale nonlinear fractional packing and covering, for multicommodity flows and network routing.
