Russian way with the mathematical travelling salesman (1979) | Hacker News Reader

Russian way with the mathematical travelling salesman (1979)

theguardian.com

46 pointsbootload10 comments

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) 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).

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.

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

Indeed. Also note that if someone found a polytime algorithm for TSP, that would imply P = NP and that would be quite a discovery.

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.

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.

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....

Also. They guy invented an algorithm for linear programming. That is _not_ the travelling salesman problem. For that, solutions need to be integer.

"Is there a link to the algorithm?"

there is now:

* https://news.ycombinator.com/item?id=9373231 (readable online)

* http://dl.acm.org/citation.cfm?id=1057529 (cite)

Thanks. Also:

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."

In Soviet Russia there are no travelling salesmen!

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).

Reply on news.ycombinator.com