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

Hinweis zur Verwendung von Bildmaterial: Die Verwendung des Bildmaterials zur Pressemitteilung ist bei Nennung der Quelle vergütungsfrei gestattet. Das Bildmaterial darf nur in Zusammenhang mit dem Inhalt dieser Pressemitteilung verwendet werden. Falls Sie das Bild in höherer Auflösung benötigen oder Rückfragen zur Weiterverwendung haben, wenden Sie sich bitte direkt an die Pressestelle, die es veröffentlicht hat.

Im Rahmen der INFORMATIK 2020 wird Dr. Jakub Tarnawski der GI-Dissertationspreis verliehen | Download

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 und vertritt seit 1969 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. Die Mitglieder binden sich an die Ethischen Leitlinien für Informatikerinnen und Informatiker der GI. Weitere Informationen finden Sie unter www.gi.de.