Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Computational Complexity - Research Seminar

Christian Engels: A Probabilistic Analysis of Karp's Partitioning Scheme for the Traveling Salesman Problem

May 20, 2008, 10:15 a.m.
E 1 3, Room 415

Traveling Salesman is an interesting problem which is not known to lie in NP (meaning, that the corresponding descicion problem is not known to be in NP). It aims at finding a Hamiltonian cycle, i.e., a cycle that visits every node exactly once, of minimum cost. Apart from the brute force solution with
n! many steps and a sophisticated technic in O(n22n), there exists different approximation schemes. This talk is about a specialisation of TSP namely Euclidean TSP and an introduction to some good approximation schemes, concentrating on Karp's Partitioning Scheme. Furthermore we will have a look at how good the tour from Karp's algorithm is in contrast to the optimal solution considering different probability settings.