What is the purpose of finding a lower bound in the Traveling Salesman Problem?

[Zurtex]

At my maths class today we just started the final module of my further maths A level class. In the lesson we met the traveling salesman problem, I understand why it is such a difficult problem and I understand why we can easily work out an upper band and why it is useful.

However our teacher did not know why we had to work out a lower bound as surely a value smaller than this would be better.

If anyone could explain this too me I would be grateful.

 

[matt grime]

The traveling salesman thing asks you to find the optimal path through the 'maze' if you will. It is important to find bounds on this, both upper and lower, so that you know roughly how long it wil take. Finding *an* upper bound is easy, as is finding a lower bound, but you would prefer to find the *largest* lower bound (and the smallest upper bound). Knowing a small bound less than some other lower bound doesn't help you anymore than knowing a bound bigger than the larger bound does.


I mean, would you rather know your test score was more than 70% or more than 10%? One clearly narrows the options down (for the better).


Just knowing the salesman travels more than 7 miles does imply he travels more than 5 miles, but knowing he travels more than 5 miles doesn't imply he travels more than 7 does it?



As it is finding the exact answer takes n! steps for n towns. If you can get a path that is at most in error by 20% say in n^2 steps you'd take it.


If you know replace you lower bound by something even smaller you decrease the effectiveness of this shortcut cos you increase the percentage error.

Is that sort of clear?

 

[Zurtex]

So rather than a way of working out a shorter route it is more a way of decreasing the amount of workings required?

 

[matt grime]

It isn't that you're working out a shorter route (what can be shorter than the shortest), but that you are finding out that the shortest route is at least as big as something. Just knowing that the shortest route is at least x miles tells you what''s going on. The aim ought to be to find the shortest route. This is very hard and takes about n! calculations for n towns. This is the complexity of it. If you figure out a way to do it very quickly yo'ure on the way to a million dollars.

We can in theory work through every possible combination of routes, but that's very time consuming, what you try and do is pick some clever way of doing it that you know it gives you an error you can live with.

If I tell you that the optimum route takes between 10 and 20 miles is that better or worse than me saying it's between 16 and 17? The larger the lower bound the better (and the smaller the top bound), but it is only an estimate that gives you more knowledge, and allows you to know if you're getting closer to the optimum. What really counts is bounding it above, absolutely.

 

[Zurtex]

Hmmm, I think I about get that thanks.