Time: 1:00pm Tuesday 9.
Location: SIT 123 Lecture Theatre
Speaker: Grigory Yaroslavtsev, Pennsylvania State University
A k-spanner of a weighted graph is a subset of edges, which preserves distances in the original graph up to a multiplicative factor k. Spanners have numerous applications, such as efficient routing, simulating synchronized protocols in unsynchronized networks, parallel, distributed and streaming algorithms for approximating shortest paths and algorithms for distance oracles.
The talk will cover recent advances in approximation algorithms for Directed K-Spanner — computational problem of finding the sparsest k-spanner of a given directed graph. Improvements in approximation for this basic problem can be naturally translated to different generalisations and related problems, such as Directed Steiner Forest, Client-Server k-spanner and others (joint work with Berman, Bhattacharyya, Makarychev and Raskhodnikova, ICALP 2011).