Algorithmen und Komplexität

Institut für Informatik – Abteilung V

Wir beschäftigen uns in der Abteilung V „Algorithmen und Komplexität“ schwerpunktmäßig mit dem Entwurf und der theoretischen Analyse von Algorithmen. Unser Ziel ist es, in verschiedenen Anwendungskontexten verbesserte Algorithmen zu entwerfen und ein tieferes Verständnis für die algorithmischen Möglichkeiten und Grenzen zu entwickeln.

Effiziente Algorithmen sind eine treibende Kraft des technischen Fortschritts der letzten Jahrzehnte. Ohne sie wären keine Suchmaschinen denkbar, die große Datenmengen in Sekundenbruchteilen durchsuchen, keine Navigationssysteme und auch keine sichere Kommunikation im Internet.

Wir forschen sowohl an grundlegenden kombinatorischen Fragestellungen im Bereich von Algorithmen und Komplexität als auch an algorithmischen Fragestellungen, die sich aus anderen Disziplinen wie der Geodäsie und der Ökonomie ergeben.

Highlights aus der Forschung

KI-Forschungsgruppe: Algorithmische Datenanalyse für die Geodäsie (AlgoForGe)

Im Rahmen der Forschungsgruppe entwickeln wir neue Algorithmen zu Fragestellungen aus dem Bereich der Geodäsie.

Zum Projekt

Exzellenzcluster: Hausdorff Center for Mathematics (HCM)

Im HCM arbeiten wir mit Kolleg*innen aus der diskreten Mathematik an grundlegenden Fragen im Bereich von Algorithmen und Komplexität.

Zum Exzellenzcluster

DFG-Sachbeihilfe: Theoretische Untersuchung praxisrelevanter Fragestellungen der Clusteranalyse

In diesem Projekt wurden neue Algorithmen im Bereich des hierarchischen Clusterings und Clusterings mit Nebenbedingungen entworfen.

Zum Projekt

Neuauflage des Lehrbuchs "Algorithmische Geometrie"

Die Neuauflage des Lehrbuchs „Algorithmische Geometrie“ von Rolf Klein, Anne Driemel und Herman Haverkort ist erschienen.

Zur Publikation

DFG-Sachbeihilfe: Verstehen von Posted Prices durch Prophet Inequalities

In diesem Projekt entwickeln wir ein besseres Verständnis, wie komplex Preise sein müssen in Szenarien mit mehreren Gütern.

Zum Projekt

Arbeitsgruppen

Die Abteilung besteht aus drei Arbeitsgruppen: Prof. Dr. Anne Driemel vertritt mit ihrer Arbeitsgruppe das Gebiet der Algorithmischen Geometrie. Die Algorithmische Geometrie ist Teilgebiet der Algorithmik mit starken Verbindungen zur Diskreten Geometrie und Kombinatorik. Algorithmische Techniken aus diesem Gebiet ermöglichen die effiziente Lösung komplexer geometrischer Probleme, was in wissenschaftlichen Anwendungen und in der Industrie zu fortschrittlichen Technologien führt.

Die Arbeitsgruppe von Prof. Dr. Thomas Kesselheim beschäftigt sich mit Algorithmischer Spieltheorie und Optimierung unter Untersicherheit. Viele typische Einsatzszenarien von Algorithmen weichen vom klassischen Schema ab, dass zu einer gegebenen Eingabe eine Ausgabe berechnet werden muss: Vorab sind nicht alle Informationen bekannt oder Algorithmen interagieren mit Agenten, die ihren eigenen Nutzen maximieren. Mithilfe eines besseren Verständnisses der Möglichkeiten und Beschränkungen entwickeln wir neue Algorithmen für verschiedene Einsatzzwecke, insbesondere für elektronische Märkte.

Die Schwerpunkte der Arbeitsgruppe von Prof. Dr. Heiko Röglin sind Analyse von Algorithmen jenseits des Worst Case sowie Algorithmen zur Clusteranalyse. Die Analyse von Algorithmen jenseits des Worst Case hat zum Ziel, ein besseres Verständnis der Algorithmen zu gewinnen und experimentelle Beobachtungen rigoros zu erklären. Dadurch werden neue Erkenntnisse gewonnen, die beim Entwurf besserer Algorithmen helfen. Clusteranalyse ist ein wichtiges Problem im Bereich der Datenanalyse, das in zahlreichen Anwendungen eine große Rolle spielt. In diesem Bereich entwickeln wir neue Algorithmen und Modelle mit dem Ziel den State of the Art zu verbessern.