Since I haven’t even finsihed explaining the optional stopping theorem yet, I thought I’d point you towards a very good post on Good Math, Bad Math explaining the max-flow min-cut theorem.
George Dantzig and the Simplex Algorithm
7 March, 2007 — optionalstoppingArs Mathematica informs me of the latest issue of Notices of the AMS, which include two features – here (pdf) and here (pdf) – on George Dantzig, who died in 2005.
An anecdote Dantzig often told was this:
During my first year at Berkeley I arrived late one day to one of Neyman’s classes. On the blackboard were two problems which I assumed had been assigned for homework. I copied them down. A few days later I apologized to Neyman for taking so long to do the homework – the problems seemed to be a little harder to do than usual. I asked him if he still wanted the work. He told me to throw it on his desk. I did so reluctantly because his desk was covered with such a heap of papers that I feared my homework would be lost there forever.
About six weeks later, one Sunday morning about eight o’clock, Anne and I were awakened by someone banging on our front door. It was Neyman. He rushed in with papers in hand, all excited: “I’ve just written an introduction to one of your papers. Read it so I can send it out right away for publication.” For a minute I had no idea what he was talking about. To make a long story short, the problems on the blackboard which I had solved thinking they were homework were in fact two famous unsolved problems in statistics. That was the first inkling I had that there was anything special about them.
Dantzig is most famous for his simplex algorithm. The simplex algorithm is a method of solving linear programming problems, that is problems that look like
Maximize
subject to
You can find out more about this remarkable algorithm – apparently one of the top 10 algorithms of all time – at the second article above (pdf), in more detail by Spyros Reveliotis, or less detail on Wikipedia.
