Skip to main content
Pressemitteilung

GI-Dissertationspreis: Neuer Algorithmus für "Problem des Handlungsreisenden"

Für seine herausragende Doktorarbeit zum mathematischen Problem des Handlungsreisenden erhält Jakub Tarnawski den Dissertationspreis der Gesellschaft für Informatik e.V. (GI)

Berlin, 30. September 2020 – Dr. Jakub Tarnawski erhält den mit 5.000 Euro dotierten GI-Dissertationspreis, eine gemeinsame Auszeichnung der Schweizer Informatik Gesellschaft (SI), der Österreichischen Computergesellschaft (OCG) und der Gesellschaft für Informatik, die herausragende Promotionsarbeiten würdigt. Die am École polytechnique fédérale de Lausanne eingereichte Forschungsarbeit widmet sich unter anderem dem mathematischen Problem des Handlungsreisenden (Traveling Salesman Problem). 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. Die Strecke von A nach B könnte zum Beispiel länger dauern oder mehr kosten als die Strecke von B nach A. Mit dem von Dr. Jakub Tarnawski im Rahmen seiner Promotion entwickelten Algorithmus lässt sich nun deutlich besser als bisher eine Annäherung an eine optimale Route berechnen. 

Die gewonnen Erkenntnisse sind insbesondere für Logistikunternehmen von hohem praktischem Nutzen. Durch die nun möglichen Verbesserungen in der Routenplanung lassen sich Zeit, Geld und CO2-Emmissionen einsparen.

GI-Präsident Prof. Dr. Hannes Federrath: „Dr. Jakub Tarnawski hat im Bereich der Informatik-Grundlagenforschung ein herausragendes Forschungsergebnis erzielt: den ersten Algorithmus, der eine zufrieden stellende Annäherung an das asymmetrische Problem des Handlungsreisenden bietet. Sowohl die Laufzeit des Algorithmus als auch der Grad der Annäherung an eine optimale Lösung sind einmalig. Darüber hinaus hat sich Herr Dr. Tarnawski einen deterministischen parallelen Algorithmus für das perfekte Matching entwickelt, der ein zweites herausragendes Forschungsergebnis darstellt. Ich gratuliere Herrn Tarnawski zu dieser hervorragenden Leistung.“

Über den GI-Dissertationspreis

Mit ihrem gemeinsam vergebenen Dissertationspreis möchten die Gesellschaft für Informatik, die Österreichischen Computer Gesellschaft und die Schweizer Informatik Gesellschaft besonders wichtige Arbeiten junger Wissenschaftlerinnen und Wissenschaftler in der Öffentlichkeit herausstellen. Die beteiligen Fachgesellschaften möchten darüber hinaus einen Beitrag zum Wissenstransfer von den Hochschulen in die Bereiche Technik, Wirtschaft und Gesellschaft leisten. Vorschlagsberechtigt für den GI-Dissertationspreis der sind alle wissenschaftlichen Hochschulen in der Bundesrepublik Deutschland, in Österreich und in der Schweiz, die das Promotionsrecht in den oben genannten Bereichen besitzen. Jede dieser Hochschulen darf eine Dissertation für den Preis vorschlagen.

 

Über die Gesellschaft für Informatik e.V.
Die Gesellschaft für Informatik e.V. (GI) ist mit rund 20.000 persönlichen und 250 korporativen Mitgliedern die größte und wichtigste Fachgesellschaft für Informatik im deutschsprachigen Raum. 2019 feiert die GI ihr 50-jähriges Gründungsjubiläum. Seit 1969 vertritt sie die Interessen der Informatikerinnen und Informatiker in Wissenschaft, Wirtschaft, öffentlicher Verwaltung, Gesellschaft und Politik. Mit 14 Fachbereichen, über 30 aktiven Regionalgruppen und unzähligen Fachgruppen ist die GI Plattform und Sprachrohr für alle Disziplinen in der Informatik. Weitere Informationen finden Sie unter www.gi.de.

Die GI-Mitglieder binden sich an die Ethischen Leitlinien für Informatikerinnen und Informatiker der Gesellschaft für Informatik e.V.: https://gi.de/ethische-leitlinien

Pressekontakt:
Frithjof Nagel
Gesellschaft für Informatik e.V. (GI)

Geschäftsstelle Berlin
im Spreepalais am Dom
Anna-Louisa-Karsch-Str.2,
10178 Berlin

Tel.: +49 30 7261 566-15
Fax: +49 30 7261 566-19
Mail: presse(at)gi.de
Web: www.gi.de

Jakub Tarnawski