University of Twente Student Theses
AverageCase Analysis of the 2opt Heuristic for the TSP
Slootbeek, J.J.A. (2017) AverageCase Analysis of the 2opt Heuristic for the TSP.

PDF
1MB 
Abstract:  The traveling salesman problem is a wellknown NPhard optimization problem. Approximation algorithms help us to solve larger instances. One such approximation algorithm is the 2opt heuristic, a local search algorithm. We prove upper bounds on the expected approximation ratio for the 2opt 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 2opt 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))). 
Item Type:  Essay (Master) 
Faculty:  EEMCS: Electrical Engineering, Mathematics and Computer Science 
Subject:  31 mathematics 
Programme:  Applied Mathematics MSc (60348) 
Link to this item:  http://purl.utwente.nl/essays/72060 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page