# Help please - Travelling salesperson lower bound

Discussion in 'Mathematics' started by Informant, Dec 14, 2011.

1. ### InformantNew commenter

AQA D1 paper (June 2006 5a)
Gill is solving a travelling salesperson problem. Write down the best upper bound chosen from 7.5, 8, 7, 7.5, 8.5 (it's 7 and I agree)
Now which is the best lower bound chosen from 6.5, 7, 6.5, 5, 7 ? They say 7, but why not the smallest value of 5?
Also, although I haven't had this question from a student yet, when applying lower bound algorithm and finding minimum connector for network with two edges removed, does this have to create a tour allowing start and finish vertex to coincide, or is a minimum spanning tree (which does not) permissible to obtain this theoretical minimum value. Textbook suggests the latter.

2. ### Daisy74

Imagine Lower bound value / solution / upper bound value
5, 6.5, 7 / solution / 7, 7.5, 8, 8.5
the closest lower bound to the solution is 7. As this case has 7 as the best upper bound the solution value will be 7. Other wise it is stated as L<= solution <= U.
The lower bound is defined as the lowest possible value for a tour, but the tour may not exist.
You don't have to find a tour for the lower bound just the minimum spanning trees. and then the highest value of (MST + 2 sides).
Imagine a cycle ABCDE is possible. If vertex A is removed BCDE may or may not be a MST, so weight of BCDE >= weight MST
weigth of AB + AE >= sum of the weights of the two shortest edges at A
So BCDE + AB + AE (which is our required solution) >= MST + sum of two removed edges.
This must work for whichever vertex is removed so we must look for the largest value of (MST + edges).
The algorithm is just finding a value that the solution will not be less than, it is not necessarily going to find a value that corresponds to a tour.
Its a difficult concept to explain - hope this goes some way to making it clearer. I found that drawing diagrams helped.