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 Teng). 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.
Simplex works well in practice but it remains open whether simplex runs in polynomial time for worst-case inputs
ReplyDeleteThis needs to be further qualified. Vanilla simplex is known to be exponential, and indeed many (most?) proposed pivoting are known to lead to exponential number of pivoting steps in the worst case. What remains an open problem is:
Does there exist a pivoting technique computable in polynomial time and leading to a polynomial number of pivoting steps of the simplex method?
Alex Lopez-Ortiz
Another "accomplishment" -- Dantzig spawned a well-known urban legend (well, not urban legend, since it was true) when he solved two open statistics problems mistaking them for homework.
ReplyDeletehttp://www.snopes.com/college/homework/unsolvable.asp
Indeed. One of my math professors liked to slip in unsolved problems into our homework. No wonder those problems were so hard!
ReplyDelete