What is the 'Traveling Salesperson' approximation ratio?

What is the 'Traveling Salesperson' approximation ratio?

Approach: Discuss polynomial time approximations for TSP.

For Metric TSP (obeying triangle inequality), the Christofides algorithm provides a 3/2 approximation ratio. For general TSP, no constant-factor approximation exists unless P=NP.

Follow-up: What is the ratio for the nearest neighbor heuristic?

Key concepts: christofides algorithm, metric tsp, triangle inequality.