Aus der Forschungsgruppe Big Data Algorithms wurden vier Papers bei SODA (Symposium on Discrete Algorithms) angenommen

Vier wissenschaftliche Papers der Forschungsgruppe “Big Data Algorithmen” wurden als Beiträge der A*-gerankten Konferenz ACM-SIAM Symposium on Discrete Algorithms (kurz: SODA) akzeptiert. SODA ist die Top-Konferenz im Bereich der Algorithmik und im Allgemein eine der angesehensten Konferenzen in der theoretischen Informatik.

Im Jahr 2025 findet die Konferenz Mitte Jänner in New Orleans statt. 

Die Forschungsgruppe “Big Data Algorithmen” besteht an der Universität Salzburg seit 2022 und wird von Prof. Sebastian Forster geleitet. Alle vier Publikationen wurden im Rahmen des von Forster mittels eines ERC Starting Grants eingeworbenen Projekts, DynASoAr, erarbeitet. Ziel des Projekts ist die Erforschung dynamischer Algorithmen, die effizient auf Veränderungen in den Eingabedaten reagieren. 

Professor Forster hat mit seinem PhD Studenten Antonis Skarlatos eine Fragestellung des unüberwachten maschinellen Lernens, die als konsistentes Clustering bekannt ist, untersucht: Wie kann eine Menge sich verändernder Punkte so um eine gegebene Anzahl an Zentren gruppiert werden, dass die Abstände der Punkte zu den Zentren möglichst geringgehalten werden und die dafür ausgewählten Zentren möglichst wenig wechseln? Die beiden Informatiker haben bewiesen, dass ein einziger Wechsel eines Zentrums nach jeder Veränderung in der Punktmenge ausreichend ist und haben somit die bisher bekannte Schranke von zwei Wechseln verbessert. 

Der Niederländer Tijn de Vos hat gemeinsam mit einem Kollegen von Dänemarks Technischer Universität neue Algorithmen für die Bestimmung der Konnektivität und der lokalen Dichte von sich dynamisch verändernden Graphen entwickelt. Die seit über 20 Jahren bestehende Schranke wurde mit dieser Entwicklung maßgeblich unterboten. Ausschlaggebend für dieses Resultat war ein strukturelles Ergebnis für die Zerlegung eines Graphs in kreislose Teilgraphen.

De Vos war seit 2020 an der Universität Salzburg tätig und hat seine Dissertation Ende November erfolgreich verteidigt. 

Mit gleich zwei Beiträgen ist Dr. Aditi Dudeja, die als Postdoc im DynASoAr Projekt angestellt ist, vertreten. Dudeja hat an der Rutgers University promoviert und ist als Expertin für Zuordnungsprobleme seit einem Jahr an der Universität Salzburg tätig. In ihrem ersten für diese Konferenz eingereichten Paper hat Dudeja mit ihren ehemaligen Kolleg:innen Färbungsprobleme in dynamischen Graphen untersucht.

Das Thema ihres zweiten Beitrags ist das Finden optimaler Paarungen in dynamischen Graphen. Dudeja und ihre Koautoren konnten zeigen, dass hierfür im Prinzip oft auf bestehende Algorithmen für “einfache” Graphen zurückgegriffen werden kann, ohne die Qualität der Lösung signifikant zu verschlechtern.