Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teoretickej informatiky - Vlado Boža (3.5.2019)

v piatok 3.5.2019 o 11:00 hod. v miestnosti M/213


30. 04. 2019 09.17 hod.
Od: Rastislav Královič

Prednášajúci: Vlado Boža

Názov:  Travelling salesman problem is NP-hard? No Problem!

Termín:  3.5.2019, 11:00 hod., M/213


Abstrakt:

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