Bounds for the travelling salesman problem Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
12 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 12 cards
- What is an upper bound for the TSP?
- The length of an actual tour; the shortest tour cannot be longer.
- What is a lower bound for the TSP?
- A value that the shortest tour cannot be less than.
- What does it mean if the upper and lower bounds are equal?
- The tour found is the shortest possible (optimal).
- How do you make an incomplete network complete?
- Join every missing pair by an arc whose length is the shortest distance between them.
- State the nearest neighbour algorithm.
- Start at a vertex, always go to the nearest unvisited vertex, then return to the start.
- Does the nearest neighbour algorithm give the shortest tour?
- Not always. It gives an upper bound.
- How do you get the best nearest neighbour upper bound?
- Start from each vertex in turn and take the smallest tour.
- How does an MST give an upper bound?
- A walk round the tree uses every arc twice, so a tour of length the MST weight exists.
- What is a shortcut?
- Going directly to the next new vertex instead of revisiting a vertex, shortening the tour.
- State the steps for a lower bound.
- Delete a vertex, find the MST of the rest, add the two shortest arcs at the deleted vertex.
- Why is the deleted-vertex method a lower bound?
- Every tour has two arcs at the vertex, and the rest is at least as long as the MST of the others.
- Which deleted vertex gives the best lower bound?
- The one giving the largest value.