Abstract
The 2-opt heuristic is a simple and popular local search heuristic for the Traveling Salesperson Problem (TSP). Albeit its performance in practice, it has exponential worst-case running-time. We consider two restrictions of the 2-opt heuristic that run in polynomial time in the worst case and analyze their approximation performance.
First, we consider X-opt, a heuristic that removes intersecting pairs of edges from two-dimensional Euclidean instances. We show that its theoretical approximation ratio is poor: the longest X-optimal tour can be approximately n/2 times longer than the optimal tour in the worst case. Moreover, even when the instance consists of n points placed uniformly at random in the unit square, the longest tour is Omega(sqrt n) times longer than the optimal tour.
Next, we propose a new heuristic, which we call Y-opt, that is defined for all TSP instances, not just Euclidean ones. Y-opt has essentially the same approximation guarantees as 2-opt, but needs only at most a cubic number of iterations in the worst case.
