University of Twente Student Theses

Login

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

Slootbeek, J.J.A. (2017) Average-Case Analysis of the 2-opt Heuristic for the TSP.

[img]
Preview
PDF
1MB
Abstract: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))).
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