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+O(φ1/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)
Average-Case Approximation Ratio of the 2-Opt Algorithm for the TSP.
Operations Research Letters, 37(2):83-84, 2009.