That's a weird article. Khachian's Algorithm is very famous as the first polynomial time algorithm for linear programming. The simplex algorithm works fantast

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.