Berufungsvortrag Gerhard Woeginger: New results on the old k-opt neighborhood

16:30 s.t - 17:45


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


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.

Zeit & Ort

16.07.2015, 16:30 s.t - 17:45

Institut für Informatik, EG, SR 005