# 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: | http://purl.utwente.nl/essays/72060 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page