Monday, 7 October 2024 @ 14:00–15:00 CEST
On-site:
University of Vienna
Seminarraum 10 (OG01)
Kolingasse 14–16
1090 Vienna
Online:
https://univienna.zoom.us/j/67032386717?pwd=g8HOG2oRrWK6T5cvmRA7bv17QRzq72.1
Practically Efficient Dynamic Algorithms for Data Centers
Abstract :
Dynamic algorithms are designed to maintain a solution while the input data undergoes a series of changes, in contrast to their traditional, "static" counterparts, which have to recompute everything from scratch as soon as the input changes. Although dynamic algorithms have received growing attention in experimental work recently, there is still a noticable gap between theory and practice.
Reconfigurable optical topologies promise to improve the performance in datacenters by dynamically optimizing the physical network in a demand-aware manner. State-of-the-art optical technologies allow to establish and update direct connectivity between top-of-rack switches within microseconds or less. However, to fully exploit temporal structure in the demand, such fine-grained reconfigurations also require fast algorithms for optimizing the direct connections to establish.
In this talk, we will first see that the problem of offloading a maximum amount of demand to the reconfigurable network can be cast as an edge-coloring problem on graphs. We will then introduce practical algorithms and evaluate their performance experimentally. The talk will conclude with some challenges and lessons learned when engineering dynamic graph algorithms in general.
Bio :
Kathrin Hanauer is a tenure-track assistant professor for Algorithms for Scalable AI at the Theory and Application of Algorithms Research Group at the Faculty of Computer Science, University of Vienna. She obtained her PhD from the University of Passau, Germany, in 2018 and did a PostDoc with Monika Henzinger at the University of Vienna.
In her current research, she focuses on algorithm engineering, especially for dynamic graph algorithms, and on building bridges between theory and practice.
