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.