Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] George Dantzig 1914-2005

Expand Messages
  • Lance
    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
    Message 1 of 1 , May 17, 2005
    • 0 Attachment
      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

    Your message has been successfully submitted and would be delivered to recipients shortly.