Bounds for the travelling salesman problem Quiz

1. A tour of length $62$ is found. The lower bound is $55$. Which statement is correct?

• A. The shortest tour is at least $62$
• B. The shortest tour is exactly $55$
• C. The shortest tour is at most $55$
• D. The shortest tour is between $55$ and $62$

2. A nearest neighbour tour from $A$ is $A$-$C$-$B$-$D$-$A$ with arcs $AC=3$, $CB=4$, $BD=6$, $DA=8$. What is the upper bound?

• A. $21$
• B. $13$
• C. $17$
• D. $15$

3. An MST has weight $25$. What upper bound does walking round it give?

• A. $25$
• B. $75$
• C. $12.5$
• D. $50$

4. To find a lower bound, which arcs at the deleted vertex are added to the MST?

• A. All of them
• B. The longest two
• C. The two shortest
• D. Only the shortest

5. A road network has $AC$ missing. The routes $A$-$B$-$C$ and $A$-$D$-$C$ have lengths $9$ and $13$. What length is given to $AC$ in the complete network?

• A. $13$
• B. $9$
• C. $22$
• D. $11$