Javascript must be enabled for the correct page display

Traveling Salesman Problem Comparisons between heuristics, linear and semidefinite programming approximations

Kruithof, M.W. (2012) Traveling Salesman Problem Comparisons between heuristics, linear and semidefinite programming approximations. Master's Thesis / Essay, Mathematics.

[img]
Preview
Text
Marielle_Kruithof_2012_TWM.pdf - Published Version

Download (842kB) | Preview
[img] Text
AkkoordDobre.pdf - Other
Restricted to Repository staff 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: http://fse.studenttheses.ub.rug.nl/id/eprint/10233

Actions (login required)

View Item View Item