Reference no: EM133217124

In every instance (i.e., example) of the TSP, we are given n cities, where each pair of cities is connected by a weighted edge that measures the cost of traveling between those two cities. Our goal is to find the optimal TSP tour, minimizing the total cost of a Hamiltonian cycle in G. Although it is NP-complete to solve the TSP, there is a simple 2-approximation achieved by first generating a minimum-weight spanning tree of G and using this output to determine our TSP tour. Prove that our output is guaranteed to be a 2-approximation, provided the Triangle Inequality holds. In other words, if OPT is the total cost of the optimal solution, and APP is the total cost of our approximate solution, clearly explain why APP≤ 2∗OPT.