Seminars

View all Seminars  |  Download ICal for this event

Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality

Series: Bangalore Theory Seminars

Speaker: Harald Räcke Technische Universität München

Date/Time: Apr 14 11:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
In a recent result Häupler, Ghaffari, and Zuzic [STOC 2021] showed that so-called h -hop oblivious routing schemes with a polylogarithmic competitive ratio exist. These can be used to solve packet routing problems almost optimally, i.e., with only a polylogarithmic loss in routing time compared to a globally optimal solution.

In this talk we present a different way of constructing h -hop oblivious routing schemes that have a weaker (sub-polynomial) competitive ratio but which can be constructed very efficiently by a distributed algorithm.

This result has important consequences in the area of distributed computing: it gives novel CONGEST algorithms for a large class of important optimization problems, including minimum-spanning tree, ( 1 + ϵ )-min-cut, ( 1 + ϵ )-shortest paths. Our algorithms solve these problems in sub-polynomial rounds on any network, as long as a sub-polynomial-round distributed algorithm exists for this network.

This is joint work with Bernhard Häupler and Mohsen Ghaffari.



Microsoft teams link:

Link


We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, Rahul Madhavan, Aditya Subramanian and Aditya Abhay Lonkar