Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Bachelor's and Master's Theses

Christian Engels: Probabilistic Analyses of Algorithms for the TSP

Bachelor's Thesis, 2008.

Advisor: Dr. Bodo Manthey

TSP is an important problem in combinatorial optimisation, for which many algorithms exist. But we still lack theoretic foundations for the performance the algorithm has in real world applications. In this paper we will try to have a look at two of these, namely Karp's Partitioning Scheme and 2-OPT. Karp's Partitioning Scheme is a construction algorithm. We will do a first smoothed analysis of this scheme. Our main result will be that E[KARP]/E[OPT] ≤ 1+O1/d/sd-1)/d) for a choosen s. The second algorithm we will look at is 2-OPT, a local search heuristic. We will do a probabilistic analysis without the constraint that the TSP instance has to fulfill the triangle inequality. Our result will be that E[length of a 2-OPT tour] ∈ O(n3/4 (ln n)1/4)

Related Publications

• [J]Christian Engels, Bodo Manthey
Average-Case Approximation Ratio of the 2-Opt Algorithm for the TSP.
Operations Research Letters, 37(2):83-84, 2009.