4 ms·

Russian way with the mathematical travelling salesman (1979)

46 points by bootload 12y ago

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 ago
  It 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 ago
    Thanks. 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."
deleted 12y ago
[deleted]
srott 12y ago
In Soviet Russia there are no travelling salesmen!
- madez 12y ago
  In Soviet Russia traveling man sells you! Fun aside, what a horrible article. It's a good reminder why you shouldn't trust the press. The press gives more opinions than information, has a political agenda and doesn't get the facts straight. An ideal information source would just deliver tuples (fact, source) and leave the evaluation to the reader. Optionally, it could provide another stream of tuples (opinion, author).
cschmidt 12y ago
That's a weird article. Khachian's Algorithm is very famous as the first polynomial time algorithm for linear programming. The simplex algorithm works fantastically well in practice, but there are problems (such as http://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube http://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube) that take exponential time. Khachian showed a polynomial time solution, although it wasn't very practical. (If memory serves from school, it was an O(n^14) algorithm. Perhaps someone can correct me if I'm remembering incorrectly.) It is also known as the ellipsoidal method (http://en.wikipedia.org/wiki/Ellipsoid_method http://en.wikipedia.org/wiki/Ellipsoid_method). None of that is directly related to the TSP. I'm not sure if he did some other work on the TSP, but he may have just been using an LP based branch and bound applied to TSP's, where the LP subproblems were solved with his algorithm.
garethrees 12y ago
There was obviously some kind of misunderstanding. Khachian found a polynomial algorithm for linear programming. And the travelling salesman problem has a formulation in terms of an integer linear program. Unfortunately, solutions to a linear program are not in general at integer points, so a solution to the real-number version of the problem doesn't, in general, solve the integer problem. See http://en.wikipedia.org/wiki/Linear_programming_relaxation http://en.wikipedia.org/wiki/Linear_programming_relaxation
- Kenji 12y ago
  Indeed. Also note that if someone found a polytime algorithm for TSP, that would imply P = NP and that would be quite a discovery.
- bitL 12y ago
  I guess they got confused - LP was probably used as a relaxation step of branch and bound for TSP (many Russian-sphere books referenced such algorithm and I think branch and bound appeared first time in literature in connection with TSP) so the author conflated the two.

46 points by bootload 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 ago
It 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 ago
  Thanks. 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."

deleted 12y ago

[deleted]

srott 12y ago

In Soviet Russia there are no travelling salesmen!

madez 12y ago
In Soviet Russia traveling man sells you! Fun aside, what a horrible article. It's a good reminder why you shouldn't trust the press. The press gives more opinions than information, has a political agenda and doesn't get the facts straight. An ideal information source would just deliver tuples (fact, source) and leave the evaluation to the reader. Optionally, it could provide another stream of tuples (opinion, author).

cschmidt 12y ago

That's a weird article. Khachian's Algorithm is very famous as the first polynomial time algorithm for linear programming. The simplex algorithm works fantastically well in practice, but there are problems (such as http://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube http://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube) that take exponential time. Khachian showed a polynomial time solution, although it wasn't very practical. (If memory serves from school, it was an O(n^14) algorithm. Perhaps someone can correct me if I'm remembering incorrectly.) It is also known as the ellipsoidal method (http://en.wikipedia.org/wiki/Ellipsoid_method http://en.wikipedia.org/wiki/Ellipsoid_method). None of that is directly related to the TSP. I'm not sure if he did some other work on the TSP, but he may have just been using an LP based branch and bound applied to TSP's, where the LP subproblems were solved with his algorithm.

garethrees 12y ago

There was obviously some kind of misunderstanding. Khachian found a polynomial algorithm for linear programming. And the travelling salesman problem has a formulation in terms of an integer linear program. Unfortunately, solutions to a linear program are not in general at integer points, so a solution to the real-number version of the problem doesn't, in general, solve the integer problem. See http://en.wikipedia.org/wiki/Linear_programming_relaxation http://en.wikipedia.org/wiki/Linear_programming_relaxation

Kenji 12y ago
Indeed. Also note that if someone found a polytime algorithm for TSP, that would imply P = NP and that would be quite a discovery.
bitL 12y ago
I guess they got confused - LP was probably used as a relaxation step of branch and bound for TSP (many Russian-sphere books referenced such algorithm and I think branch and bound appeared first time in literature in connection with TSP) so the author conflated the two.