Wow, the article didn't even mention the "original" solve of the 48 US city problem (one in each state) in 1954 (they included Washington D.C., so 49 to be prec

Wow, the article didn't even mention the "original" solve of the 48 US city problem (one in each state) in 1954 (they included Washington D.C., so 49 to be precise)! For those interested, Dantzig (creator of the simplex method), Fulkerson and Johnson made quite the stir when they tried out the TSP at Rand in California more than half a century ago in their paper, "Solution of a large scale traveling salesman problem" [1]. The paper contains a historical context of the problem and their methods towards finding and proving (important!) that their solution was in fact optimal. For those interested in Dantzig, he was the famed PhD student who came late to class one day and wrote down two open problems mistakenly thinking it was homework. He ended up using those solutions as a portion of his PhD thesis [2]. Here's an excerpt from Dantzig himself: It happened because during my first year at Berkeley I arrived late one day at one of [Jerzy] Neyman's classes. On the blackboard there were two problems that 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 than usual. I asked him if he still wanted it. 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, [my wife] 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 that 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. A year later, when I began to worry about a thesis topic, Neyman just shrugged and told me to wrap the two problems in a binder and he would accept them as my thesis. The second of the two problems, however, was not published until after World War II. It happened this way. Around 1950 I received a letter from Abraham Wald enclosing the final galley proofs of a paper of his about to go to press in the Annals of Mathematical Statistics. Someone had just pointed out to him that the main result in his paper was the same as the second "homework" problem solved in my thesis. I wrote back suggesting we publish jointly. He simply inserted my name as coauthor into the galley proof. [1] http://www.iro.umontreal.ca/~gendron/IFT6551/LECTURES/TSP.pdf http://www.iro.umontreal.ca/~gendron/IFT6551/LECTURES/TSP.pd... [2] http://www.snopes.com/college/homework/unsolvable.asp http://www.snopes.com/college/homework/unsolvable.asp