tag:blogger.com,1999:blog-3722233.post111637642289073881..comments2024-08-06T20:16:40.851-05:00Comments on Computational Complexity: George Dantzig 1914-2005Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-1116462582021474112005-05-18T19:29:00.000-05:002005-05-18T19:29:00.000-05:00Indeed. One of my math professors liked to slip i...Indeed. One of my math professors liked to slip in unsolved problems into our homework. No wonder those problems were so hard!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116432923735491222005-05-18T11:15:00.000-05:002005-05-18T11:15:00.000-05:00Another "accomplishment" -- Dantzig spawned a well...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.<BR/><BR/>http://www.snopes.com/college/homework/unsolvable.aspAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1116383732834212822005-05-17T21:35:00.000-05:002005-05-17T21:35:00.000-05:00Simplex works well in practice but it remains open...<I>Simplex works well in practice but it remains open whether simplex runs in polynomial time for worst-case inputs</I><BR/><BR/>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:<BR/><BR/>Does there exist a pivoting technique computable in polynomial time and leading to a polynomial number of pivoting steps of the simplex method?<BR/><BR/>Alex Lopez-OrtizAnonymousnoreply@blogger.com