University of Twente Student Theses
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.
|
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: | https://purl.utwente.nl/essays/72060 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page