4 ms·
There was obviously some kind of misunderstanding. Khachian found a polynomial algorithm for linear programming. And the travelling salesman problem has a formu
by garethrees 11y 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 11y agoIndeed. Also note that if someone found a polytime algorithm for TSP, that would imply P = NP and that would be quite a discovery.
- bitL 11y agoI 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.