Gerhard Woeginger, Technische Universität Eindhoven, Niederlande

Raum SR005

16:30 - 17:00 Lehrprobe k-Median Problem

17:00 - 17:45 New results on the old k-opt neighborhood

Abstract:

k-Opt is one of the most popular local search heuristics for the Travelling Salesman Problem (TSP); k-Opt tries to improve a (suboptimal) tour by removing k edges and by reconnecting the resulting pieces into a new tour by inserting k new edges.

In the talk, I will concentrate on the question whether a given tour is a local optimum for k-opt (for some fixed k), and I will present a fine-grained complexity analysis of this problem.