Kruithof, M.W. (2012) Traveling Salesman Problem Comparisons between heuristics, linear and semidefinite programming approximations. Master's Thesis / Essay, Mathematics.
|
Text
Marielle_Kruithof_2012_TWM.pdf - Published Version Download (842kB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
Text
AkkoordDobre.pdf - Other Restricted to Registered users only Download (32kB) |
Abstract
In this thesis we investigate linear and semidefinite programming approximations for the Traveling Salesman Problem: the problem of finding the tour of minimum length that visits each city exactly ones. We conduct numerical comparisons between the Held-Karp and the Van der Veen relaxations for the symmetric circulant Traveling Salesman Problem. Out of these comparisons we conjecture that these bounds are equal. Furthermore, we construct a heuristic to find a tour out of the solution matrix of the best existing semidefinite programming approximation of the Traveling Salesman Problem. Most of the time our method gives a tour value closer to the optimum than existing tour construction methods like nearest-neighbor and farthest insertion.
| Item Type: | Thesis (Master's Thesis / Essay) |
|---|---|
| Degree programme: | Mathematics |
| Thesis type: | Master's Thesis / Essay |
| Language: | English |
| Date Deposited: | 15 Feb 2018 07:48 |
| Last Modified: | 15 Feb 2018 07:48 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/10233 |
Actions (login required)
 |
View Item |