Für seine herausragende Doktorarbeit zum mathematischen Problem des Handlungsreisenden erhält Jakub Tarnawski den Dissertationspreis der Gesellschaft für Informatik e.V. (GI). Die am École polytechnique fédérale de Lausanne eingereichte Forschungsarbeit widmet sich unter anderem dem mathematischen Problem des Handlungsreisenden (Traveling Salesman Problem).
Dr. Jakub Tarnawski. Foto: Gesellschaft für Informatik
Die Herausforderung besteht darin, eine optimale Reise-Route für den Besuch mehrerer Orte zu finden. Dabei muss jede Station mindestens einmal besucht werden, jedoch soll die Reisestrecke des Handlungsreisenden möglichst kurz sein und die erste Station der letzten Station entsprechen. In der einfachen, der symmetrischen Variante, sind die Kosten, die Zeit oder das Unfallrisiko einer Strecke unabhängig davon in welcher Richtung sie zurückgelegt wird. In der erschwerten, asymmetrischen Variante des Problems, hängen die Widrigkeiten einer Strecke davon ab, in welcher Richtung sie zurückgelegt wird. Mit dem von Dr. Jakub Tarnawski im Rahmen seiner Promotion entwickelten Algorithmus lässt sich nun besser als bisher eine Annäherung an eine optimale Route berechnen. Der mit 5.000 Euro dotierte GI-Dissertationspreis ist eine gemeinsame Auszeichnung der Schweizer Informatik Gesellschaft (SI), der Österreichischen Computergesellschaft (OCG) und der Gesellschaft für Informatik.