---
created_at: '2015-04-14T02:49:29.000Z'
title: Russian way with the mathematical travelling salesman (1979)
url: http://www.theguardian.com/technology/2014/oct/29/mathematics-khachian-russia-travelling-salesman-archive-1979
author: bootload
points: 46
story_text: 
comment_text: 
num_comments: 10
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1428979769
_tags:
- story
- author_bootload
- story_9371847
objectID: '9371847'
year: 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.
