Forschung
Die Forschungsarbeiten des Lehrstuhls liegen in der Entwicklung und Analyse von effizienten Algorithmen, einer grundlegenden Disziplin in der Informatik. Der Algorithmenentwurf ist verbunden mit der Konstruktion geeigneter Datenstrukturen und komplexitätstheoretischen Untersuchungen.
Ein Schwerpunkt der wissenschaftlichen Arbeiten liegt auf der Entwicklung von Online- und Approximationsalgorithmen. Dabei werden algorithmische Problem untersucht, die schwer oder gar nicht exakt gelöst werden können. Viele Optimierungsprobleme, die in der Praxis auftreten, sind online, d.h. relevanter Input trifft nach und nach im Laufe der Zeit ein. Ein Online-Algorithmus muss kontinuierlich Output berechnen, ohne zukünftigen Input zu kennen. Aufgrund dieses Handicaps, die Zukunft nicht zu kennen, sind in der Regel keine optimalen Lösungen möglich. Wohl bekannt und in praktischen Anwendungen ebenfalls sehr relevant sind NP-harte Optimierungsprobleme. Diese können in Polynomialzeit nicht optimal gelöst werden, wenn man davon ausgeht, das die Komplexitätsklassen P und NP nicht gleich sind (P ≠ NP). Ziel in beiden Bereichen ist die Entwicklung von Algorithmen, die beweisbar gute Näherungslösungen berechnen.
Weitere Forschungsinteressen der Arbeitsgruppe liegen im Bereich der algorithmischen Spieltheorie. Untersucht werden Informatik-Probleme, bei denen eine Vielzahl von autonomen Agenten beteiligt ist. Gesucht sind stabile Zustände, sogenannte Nash-Gleichgewichte, bei denen kein Agent einen Anreiz hat, von seiner aktuellen Strategie abzuweichen. Relevant ist deren Güte relativ zum Optimum (Price of Anarchy, Price of Stability).
Schießlich haben wir im Bereich des Algorithm Engineering gearbeitet, einem Vorgehen, bei dem Algorithmenentwurf, Analyse und Implementierung ineinandergreifen und sich wechselseitig ergänzen. Auf diese Weise kann die Kluft zwischen Theorie und Praxis überbrückt werden.
Projekte (Auswahl)
DFG-Graduiertenkolleg AdONE
Das DFG-geförderte Graduiertenkolleg “Advanced Optimization in a Networked Economy (AdONE)” untersucht den effizienten Einsatz knapper und kostspieliger Ressourcen in der vernetzten Wirtschaft. Dieses Doktorandenprogramm ist interdisziplinär in der Mathematik, der Informatik und den Wirtschaftswissenschaften angelegt. Beteiligt sind die TUM School of Management und die TUM School of Computation, Information and Technology.
DFG-Graduiertenkolleg ConVeY
Das DFG-geförderte Graduiertenkolleg “Continuous Verification of CYber-Physical Systems (ConVeY)” studiert cyber-physische Systeme, in die zunehmend Netzwerke, Computer, Sensoren und Aktuatoren integriert sind. Diese komplexen Systeme arbeiten oftmals in sicherheitskritischen Umgebungen und müssen mit dem kontinuierlichen Verhalten ihrer Umwelt umgehen. Ziel dieses Doktorandenprogramms ist die Entwicklung von Techniken zur Verizifizierung solcher Systeme. Dabei liegt ein Fokus auf KI-Methoden. Das Graduiertenkolleg ist angesiedelt im Institut für Informatik der LMU und dem Department of Computer Science der TUM.
BMBF-Forschungshub 6G-life
Der vom Bundesministerium für Bildung und Forschung (bzw. BMFTR) geförderte Hub 6G-life betreibt innovative Forschung zu 6G-Kommunikationsnetzen. Dazu werden grundlegende Fragen zur Datenübertragung und zu verteilten Rechenressourcen im Netz untersucht. Ziel ist auch die Entwicklung neuer Ansätze für Nachhaltigkeit, Sicherheit, Belastbarkeit und Latenzzeit. Der Hub ist angesiedelt an der TU Dresden und an der TU München. Der Lehrstuhl war von 2021 bis 2025 beteiligt.
ERC Advanced Grant: Algorithmic Performance Guarantees
Dieses Projekt studierte algorithmische Leistungsgarantien für klassische und moderne Optimierungsprobleme, die oftmals nicht exakt gelöst werden können. Dabei wurden Forschungsfragen untersucht, die zum Teil viele Jahre bzw. Jahrzehnte ungelöst waren oder aber in modernen Anwendungen auftreten. Das Spektrum an Forschungsthemen umfasste (a) die Ressourcenverwaltung in Computersystemen, (b) Datenstrukturen, (c) Graphenprobleme und Verbindungen zur Internet-Werbung, (d) komplexe Netzwerke und (e) massiv parallele Systeme. Das Projekt wurde vom European Research Council (ERC) von 2016 bis 2021 mit 2,5 Mio Euro gefördert.
DFG-Projekt Energieeffizientes Scheduling
Dieses Projekt war Teil des DFG-Schwerpunktprogramms 1736 “Algorithmen für große Datenmengen”, das von 2014 bis 2023 gefördert wurde. Ziel des Projekts zum energieeffizienten Scheduling war die Untersuchung algorithmischer Techniken, die Energie in Hardwareumgebungen einsparen und somit die Verarbeitung von großen Datenmengen auf Systemebene unterstützen. Ein Arbeitsfokus lag auf der Technik des Dynamic Speed Scalings.
Förderung im Gottfried Wilhelm Leibniz-Programm der DFG
Verbunden mit dem Gottfried Wilhelm Leibniz-Preis für Susanne Albers im Jahr 2008 war eine Forschungsförderung im Umfang von 2,5 Mio Euro, die völlig frei und ohne administrativen Aufwand für weitere wissenschaftliche Arbeiten in den Jahren 2009 bis 2015 eingesetzt werden konnten. Ein besonderer Dank gilt der Deutschen Forschungsgemeinschaft (DFG)!