Approximation Algorithms for the (Asymmetric) Traveling Salesman Problem

Beschreibung

Der Vortrag wird auf Englisch gehalten und findet als Teams Live-Ereignis statt. Der Einwahl-Link wird hier in der Vortragsankündigung veröffentlicht.

Abstract:
The famous Traveling Salesman Problem (TSP) asks: given a graph with weights on edges, what is the shortest tour that visits all vertices? As TSP is NP-hard, the theoretical study of algorithms for TSP has focused on approximation algorithms - ones that are provably both efficient and give solutions competitive with the optimum. In this talk I will give a short introduction to approximation algorithms for TSP. In particular, I will discuss the first constant-factor approximation algorithm for the asymmetric version of TSP (ATSP), where the graph is directed, which is a 2017 joint work with Ola Svensson and László Végh. This will serve as a nice example of how linear programming is a very useful technique in the design of algorithms for discrete problems.

Kurzvita:
Jakub Tarnawski ist Algorithmenforscher bei Microsoft Research. Er interessiert sich umfassend für theoretische Informatik und kombinatorische Optimierung, insbesondere für Graphenalgorithmen und Approximationsalgorithmen. Bei seiner Arbeit widmet er sich grundlegenden Problemen auf diesen Gebieten, wie etwa dem Handlungsreisenden-Problem, der submodularen Maximierung, dem Matching, und verschiedenen Scheduling-Varianten. Er ist Träger des Best Paper Award des STOC 2018 fürseine Arbeit zum Handlungsreisenden-Problem sowie des Best Paper Award des FOCS 2017 für seine Arbeit zu Paarungen. 2019 promovierte Jakub Tarnawski an der EPFL unter Anleitung von Ola Svensson zum Doktorder Informatik. Seine Dissertation wurde mit dem Chorafas Foundation Prize, der EPFL Thesis Distinction sowie dem Dissertationspreis 2019 der GI ausgezeichnet. Seine Master-Abschlüsse in Mathematik und Informatik erhielt er von der Universität Wrocław, Polen.

Der Vortrag findet als Online-Event statt. Einwählen können Sie sich bei Microsoft-Teams.