3.6 KiB
| created_at | title | url | author | points | story_text | comment_text | num_comments | story_id | story_title | story_url | parent_id | created_at_i | _tags | objectID | year | |||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2015-04-14T02:49:29.000Z | Russian way with the mathematical travelling salesman (1979) | http://www.theguardian.com/technology/2014/oct/29/mathematics-khachian-russia-travelling-salesman-archive-1979 | bootload | 46 | 10 | 1428979769 |
|
9371847 | 1979 |
A young Soviet mathematician, apparently totally unknown to any of the world’s senior practitioners, has found an answer to one of the most baffling problems in computer calculation.
But his obscurity is such that his discovery went unnoticed for 10 months in the mathematical world, although work on the problem has been going on for years.
The apparent breakthrough was achieved by L. G. Khachian, and was published in a Soviet scientific journal, Doklady, last January. Few people in the West read the journal and it was only after rumours of the discovery circulated at a conference in Germany that anyone in the mathematical world at large had even a hint that someone had come up with an answer to what is known in the trade as the “travelling salesman” problem.
The fact that some of the world’s best brains have been trying to solve the problem gives some idea of its density to the layman. Reduced to its simplest, the difficulty is to find a formula for a computer to work out the best route for a salesman to take when he has to make calls in a number of different cities.
This is only a sample problem. There are any number of analogous situations in the everyday life of the industrial world: calculating the most efficient way of staffing a factory with three shifts of workers is another.
On the face of it, this should present no difficulty at all and, up to a point, the computer can do the sums at its normal speed. But it only needs a small increase in the number of cities to be visited by the salesman for the machine to fall into the binary version of a nervous breakdown.
The trouble is that the machine can only be programmed to work on the problem through trial and error, laboriously going through all the possible combinations until one emerges which is better than all the others - known in the trade as the exponential time method.
The alternative being sought would use the polynomial time method, by which the machine can carry out a whole range of simultaneous calculations.
A route for a salesman visiting 60 cities would take about one-fifth of a second to work out with a polynomial formula. Using exponential time methods it needs literally billions of centuries. But no one so far has managed to come up with a mathematical theory to underpin a solution.
Now Mr Khachian has burst on the scene and seems to have provided a significant bit of the answer. Since no one knows who he is and since there is no record of any previous publication by him, the speculation is that he carried out his work as part of his doctoral thesis.
The best brains in the business have tried out his formula and agree that it works, at least on a pocket calculator. It has yet to be given a full-blown test as part of a computer programme.
Mr Khachian’s solution is not easily explained, but involves the use of sets (that central element in the new maths) in a more imaginative way than hitherto which closes in on the best solution.
The practical advantage of this is to cut out consideration of obvious non-starters. The consensus of the mathematical fraternity is that the Russian’s obscurity is not likely to last if he continues to produce work of this calibre.