For the seminar "Selected Fields in Computer Science" offered by Prof. Dr. R. Schrader in summer 2013 at the University of Cologne I dealt with the concept of local search and presented the resulting K-Opt Algorithm for the NP-complete Travelling salesman problem that gives results with a quality determined by the choice of k.

Furthermore my seminar paper covered the Lin-Kernighan-Heuristic which is an in the real world often used heuristic algorithm for getting approximate solutions for the TSP that are usually > 95% of the optimum for real world data.

The seminar paper is in German and can be downloaded here: K-Opt and the Lin-Kernighan-Heuristic for the Traveling Salesman Problem (German)