Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 21, 2021, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Goran Zuzic
Single source shortest path is one of the oldest and most well-studied problems in computer science. Recently, significant strides in our understanding of the problem have been made on account of modern and somewhat counterintuitive continuous optimization techniques. However, many important open questions have been unanswered, including how to design (universally-)optimal (1+eps)-approximate distributed shortest path algorithms, where universally-optimal means that they closely match the lower bound on each graph they are being run on. We resolve this question in a very recent work set to appear in SODA 2022 by combining the prior continuous optimization ideas with a new and notably simple way of obliviously approximating transshipment cost (also known as optimal transport or Wasserstein distance) in any graph. In this talk, I will give a short overview of the modern techniques used to tackle the shortest path problem. Furthermore, I will also present the new ideas required to obtain universally-optimal shortest path algorithm in the distributed setting. Based on joint work with Bernhard Haeupler, Gramoz Goranci, Xiaorui Sun and Mingquan Ye.
Automatic MiSe System Software Version 1.4803M | admin login