Ein Angebot des JRZ ISIA
Die Reading Group hat den Charakter eines lockeren Fachseminars mit Vorträgen einer Länge zwischen 30 und 45 Minuten und anschließender Diskussion. In freundlicher Atmosphäre und unter weitestgehender Themenfreiheit werden etwa Forschungsergebnisse, wissenschaftliche oder technologische Überblicksvorträge oder die Aufbereitung einer Forschungsfrage präsentiert und diskutiert. Der Fokus liegt im Austausch, in der Diskussion. Organisatorische Fragen, Anmeldungen zu Vorträgen oder Vortragsvorschläge bitte an Stefan Huber richten.
Termine 2025
November, 25th, 2025 13.30 pm, Sebastian Forster (PLUS) | An Update to Dynamic Graph Algorithms
Abstract: From a procedural viewpoint, an algorithm is a list of instructions that transforms a given input into the desired output. In many scenarios the input is not given to the algorithm in its entirety from the start and might undergo changes that the algorithm needs to react to. Dynamic algorithms are a class of algorithms that are specifically designed to quickly adapt their output after an update to the input data. In the past years, near-optimal dynamic algorithms have been designed for many "textbook" problems and a successful research program has been established around using dynamic algorithms to speed up static algorithms. However, these theory-driven efforts have arguably created little real-world impact. In this talk, I propose a systematic focus shift for dynamic algorithms towards problems relevant to practitioners in domains like network science and machine learning. As a case study, I present recent work on dynamic k-center clustering on evolving graphs: we give the first efficient approximation algorithms for updating the k-center clustering of a graph undergoing edge insertions and/or deletions. Broadly speaking, the goal of this research agenda is to find novel applications of dynamic algorithms in science and technology.
If you want to join, please send an email to Stefan Huber.