Tuesday, May 17, 2005

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 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.

3 comments:

  1. Simplex works well in practice but it remains open whether simplex runs in polynomial time for worst-case inputs

    This 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

    ReplyDelete
  2. 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.

    http://www.snopes.com/college/homework/unsolvable.asp

    ReplyDelete
  3. Indeed. One of my math professors liked to slip in unsolved problems into our homework. No wonder those problems were so hard!

    ReplyDelete