Seminars
View all Seminars | Download ICal for this eventHop-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