EADS Talk by Sebastian Krinninger


Approximate Single-Source Shortest Paths in Distributed Networks


In this talk, I present recent advances on computing approximate solutions to the fundamental single-source shortest paths problem in the CONGEST model of distributed computing. I will outline two orthogonal
frameworks for obtaining almost tight algorithms in undirected graphs.

The first framework is combinatorial and revolves around the task ofefficiently constructing a sparse hop set to speed up standard algorithms by reducing the hop diameter of the graph. The second framework leverages techniques from continuous optimization and actually
addresses a more general problem: computing an

approximate solution to the shortest transshipment problem. While the second framework gives superior running time bounds, improvements in the first framework would potentially transfer directly to the PRAM model.

Joint work with Ruben Becker, Monika Henzinger, Andreas Karrenbauer,
Christoph Lenzen, and Danupon Nanongkai.