Seminar of Theoretical Computer Science - Vlado Boža (3.5.2019)

Friday 3.5.2019 at 11:00, room M/213

30. 04. 2019 09.23 hod.
By: Rastislav Královič

Vlado Boža:
Travelling salesman problem is NP-hard? No Problem!

Abstract:
I will talk about practical solutions for travelling salesman problem (mainly approaches in LKH and little bit from Concorde). These tools produce almost optimal solutions for many practical instances of TSP. We will show how these tools produce good solutions and also how they prove they their solution is almost optimal.

I will also talk about our experience from Kaggle competitions about variants of TSP: https://www.kaggle.com/c/traveling-santa-problem
https://www.kaggle.com/c/traveling-santa-2018-prime-paths

web: https://beda.dcs.fmph.uniba.sk/seminar