Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 02, 2023, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: David Ellis Hershkowitz
Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as h-length flows which are defined as flows whose flow paths are restricted to have length at most h. Many well-studied algorithmic primitives---such as maximal and maximum length-constrained disjoint paths---are special cases of h-length flows. Likewise the optimal h-length flow is a fundamental quantity in network optimization, characterizing, up to poly-log factors, how quickly a network can accomplish numerous distributed primitives. We give the first efficient algorithms for computing (1 - eps)-approximate h-length flows that are ``as integral as possible.'' We give deterministic algorithms that take ~O(m*poly(h)) sequential time and poly(h)*2^(O(sqrt(log n))) distributed time. We use these algorithms to simplify deterministic distributed algorithms for computing expander decompositions and to give the first efficient, distributed and deterministic (1 - eps)-approximation algorithms for bipartite b-matching. Joint work with Bernhard Haeupler and Thatchaphol Saranurak.
Automatic MiSe System Software Version 1.4803M | admin login