5 ms·
Holy crap! Is there a link to the algorithm? It sounds like he arranges vertexes into sets composed of their closest neighbors and then performance a sort of me
by gnarbarian 12y ago
Holy crap! Is there a link to the algorithm? It sounds like he arranges vertexes into sets composed of their closest neighbors and then performance a sort of merge sort to get a circuit.
- jpfr 12y agoIt took them some time to notice. But his results are actually very well-known today. Here's a more thorough account of the story. http://onlinelibrary.wiley.com/doi/10.1002/j.2326-1951.1980.tb01345.x/abstract http://onlinelibrary.wiley.com/doi/10.1002/j.2326-1951.1980.... Also. They guy invented an algorithm for linear programming. That is _not_ the travelling salesman problem. For that, solutions need to be integer.
- bootload 12y ago"Is there a link to the algorithm?" there is now: * https://news.ycombinator.com/item?id=9373231 https://news.ycombinator.com/item?id=9373231 (readable online) * http://dl.acm.org/citation.cfm?id=1057529 http://dl.acm.org/citation.cfm?id=1057529 (cite)
- acqq 12y agoThanks. Also: http://en.m.wikipedia.org/wiki/Linear_programming http://en.m.wikipedia.org/wiki/Linear_programming "The linear-programming problem was first shown to be solvable in polynomial time by Leonid Khachiyan in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior-point method for solving linear-programming problems."