Khachian's Algorithm

SOVIET DISCOVERY ROCKS MATHEMATICAL WORLD

Last November, sensational headlines appeared widely in the news amid reports of a startling discovery by a previously unheralded Russian mathematician, L.G. Khachian. The reports predicted that the discovery would not only revolutionize the field of linear programming, but also solve integer programming problems, such as the famous traveling salesman problem. (A salesman plans to visit a number of cities. If time and money are no object, he can visit the cities in any order. But they are, and he cannot. There is at least one shortest route that passes through all the cities; the problem is to find one.)