Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, October 21, 2021, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Goran Zuzic

Universally-Optimal (1+eps)-Approximate Shortest Path and Transshipment in the Distributed Setting

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login