Average-Case Analysis of the 2-opt Heuristic for the TSP

The traveling salesman problem is a well-known NP-hard optimization problem. Approximation algorithms help us to solve larger instances. One such approximation algorithm is the 2-opt heuristic, a local search algorithm. We prove upper bounds on the expected approximation ratio for the 2-opt heuristic for the traveling salesman problem for three cases. When the distances are randomly and independently drawn from the uniform distribution on [0; 1] we show that the expected approximation ratio is O(Sqrt(n log(n))). For instances where the distances are 1 with probability p and 2 otherwise, we prove a bound for fixed p strictly between 0 and 1 that gives an upper bound on the number of heavy edges in the worst local optimum solution with respect to the 2-opt heuristic of O(log(n)). For instances where the edges distances are randomly and independently drawn from the exponential distribution, we can upper bound the expected approximation ratio by O(Sqrt(n log³(n))).