What approaches exist for solving the Traveling Salesman Problem?

TSP is NP-hard; exact solutions are O(n!). DP with bitmask achieves O(n^2 * 2^n) - dp[mask][i] = min distance visiting cities in mask, ending at i. Approximation algorithms: Christofides (1.5x optimal for metric TSP), MST-based (2x optimal). Heuristics: Nearest neighbor, 2-opt improvement, simulated annealing, genetic algorithms. Branch and bound with good bounds can solve instances with ~50-100 cities. Choice depends on size and accuracy requirements.