[Computational Complexity] George Dantzig 1914-2005
George Dantzig passed away last Friday. In the 1940s Dantzig invented linear programming and developed the simplex method for solving LP.
Simplex works well in practice but it remains open whether simplex runs in polynomial time for worst-case inputs (though see this paper by Spielman and Tang). Dantzig's death comes just two weeks after the passing of Leonid Khachiyan who had the first provably efficient algorithm for linear programming three decades after Dantzig developed the simplex method. Khachiyan's ellipsoid algorithm is not at all practical as compared with the simplex method.
Posted by Lance to Computational Complexity at 5/17/2005 07:32:00 PM