Operations Research Combinatorial Optimization question, bottleneck traveling salesman problem (TSP). triangle inequality, hamiltonian cycle, minimum spanning tree (MST)

Question 11: (10 points) In the metric bottleneck traveling salesman problem we have a complete graph with distances satisfying the triangle inequality, and we want to find a Hamiltonian cycle such that the cost of the most costly edge in the cycle is minimized. A bottleneck minimum spanning tree (MST) of a graph G is a spanning tree minimizing the heaviest edge used. (a) (2 points) Argue that it is possible to find an optimal bottleneck MST in polynomial time. (Use that in any graph an MST can be found in polynomial time.) (b) (2 points) Show that it is possible to construct a walk visiting all vertices in a bottleneck MST exactly once without short cutting more than 2 consecutive vertices. (This answer may be hard to find.) (c) (3 points) Give a 3-approximation algorithm for bottleneck TSP. (If you have no good answer to (a) or (b) then you can still answer (c) using the statements of (a) and (b).) (d) (3 points) Show that there is no -approximation algorithm for metric bottleneck TSP with