Algorithms & Complexity

Algorithms & Complexity deckt ein breites Spektrum grundlagenorientierter und angewandter Arbeitsrichtungen in der Algorithmik ab. Ziel ist es, Algorithmen zu entwickeln und ihre Performanz bezüglich eines gewünschten Qualitätsmaßes zu analysieren. Die Schwerpunkte liegen unter anderem auf der Erforschung von Approximations- und Online-Algorithmen. Diese sollen helfen, Näherungslösungen für Probleme zu entwickeln, die sich nur schwer oder gar nicht exakt lösen lassen. Algorithms & Complexity zielt auf die Entwicklung von Algorithmen ab, die ein beweisbar gutes Verhalten erzielen. Untersucht werden insbesondere Probleme, die in der Ressourcenverwaltung von Computersystem, in großen Netzwerken sowie in der Datenstrukturierung auftreten.

• Randomisierte Algorithmen. Randomisierte Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und effizienter als deterministische Algorithmen für dasselbe Problem. Algorithms & Complexity entwickelt und analysiert randomisierte Algorithmen für grundlegende Optimierungsprobleme.
• Parallel- und Netzwerk-Algorithmen. Netzwerk- und Graphen-Algorithmen dienen der Optimierung von Abläufen in verschiedensten Anwendungsbereichen. Die Forschung auf dem Gebiet der parallelen Algorithmen untersucht parallele Rechnerarchitekturen und entwickelt parallele Algorithmen für grundlegende Probleme.
• Algorithmischer Spieltheorie. Dabei handelt es sich um ein junges Forschungsgebiet an der Schnittstelle von theoretischer Informatik, Mathematik und Betriebswirtschaftslehre, da es sich mit dem optimalen strategischen Verhalten in interaktiven Situationen befasst.
• Algorithm Engineering. Hier hat die Forschung in einigen Bereichen bereits erfolgreich dazu beigetragen, die Kluft zwischen Theorie und Praxis zu überbrücken. Paradebeispiele sind die rasanten Fortschritte, die sich durch neue Algorithmen für die Routenplanung oder die Suchfunktion in Texten erzielen ließen. Es werden experimentelle Studien durchgeführt, in denen die durch mathematische Analysen gewonnenen Forschungsergebnisse validiert werden.
• Energieeffiziente Algorithmen. Da auch Rechen- und Datenzentren von den stark gestiegenen Energiekosten betroffen sind, untersucht Algorithms & Complexity algorithmische Techniken, die den Energiebedarf in Computersystemen reduzieren.

Algorithms & Complexity untersucht im Bereich der Anwendung grundlegende algorithmische und komplexitätstheoretische Probleme in der Berechnungslogik, der Programm- und Systemverifikation, der mathematischer Optimierung, der Bilderkennung sowie im wissenschaftlichen Rechnen. In diesem Kontext werden verschiedene Effizienz- und Komplexitätsmaße untersucht. Außerdem werden Algorithmen für massiv-parallel Architekturen entwickelt, in denen eine riesige Anzahl von Prozessoren über ein Netzwerk verbunden sind.

DFG Priority Programme 1736 "Algorithms for Big Data"

Algorithms for BIG DATA

Energy-efficient Scheduling

Partner: Prof. Susanne Albers

Dieses Projekt erforscht algorithmische Techniken zur Energieeinsparung in Hardwareumgebungen. Es unterstützt damit die Verarbeitung großer Datenmengen auf Systemebene. Im Mittelpunkt steht die Methode des Dynamic Speed Scaling. Der Großteil der in der Literatur existierenden Arbeiten geht von idealisierten Annahmen bezüglich der Prozessorarchitektur aus: Es wird angenommen, ein Prozessor habe ein kontinuierliches, unbegrenztes Geschwindigkeitsspektrum und könne Änderungen in der Geschwindigkeit jederzeit verlustfrei vornehmen. Das Projekt entwickelt und analysiert Algorithmen für ein realistisches Szenario, in dem ein Prozessor über eine endliche Menge von diskreten Geschwindigkeiten verfügt. Experimente, welche die Algorithm-Eingineering-Komponente des Projekts bilden, ergänzen hierbei die theoretisch orientierte Forschungsarbeit. Algorithmische Ergebnisse sollen im Rahmen des Projektes stärker für die Praxis nutzbar werden.

Energy-efficient Scheduling

Gottfried Wilhelm Leibniz-Preis für Prof. Susanne Albers

Die Auszeichnung unterstützt die Forschung in einem weiten, fast unbegrenzten Themenspektrum in der Entwicklung und Analyse von Algorithmen, der algorithmischen Spieltheorie und des Algorithm Engineering. Die Arbeiten konzentrieren sich auf den wissenschaftlichen Fortschritt im Bereich der Online- und Approximationsalgorithmen. Die Studien betreffen insbesondere grundlegende Probleme in der Ressourcenverwaltung von Computersystemen, das Prozessorscheduling, Netzwerkdesignspiele und energieeffiziente Algorithmen.

Gottfried Wilhelm Leibniz-Preis

Geometrische Rekonstruktion in refraktions- und diffraktionsbasierter Tomografie

Partner: Prof. Peter Gritzmann Im Zentrum steht die mathematische Modellierung und Analyse von Problemen in der (dynamischen) Tomografie sowie die Entwicklung von Algorithmen basierend auf Geometrie und kombinatorischer Optimierung.

Gradschranken für Gröbnerbasen wichtiger Klassen von Polynomidealen und effiziente Algorithmen

Partner: Prof. Ernst Mayr

Im Jahr 1965 führte Buchberger in seiner Dissertation Gröbnerbasen ein, um Probleme der Computeralgebra algorithmisch zu lösen. Das grundlegendste Beispiel ist das Wortproblem für Polynomideale, welches darin besteht zu entscheiden, ob ein gegebenes Polynom Element eines gegebenen Ideals ist. Buchberger konnte einen Algorithmus präsentieren, mit dem sich eine Gröbnerbasis für jedes Polynomideal berechnen lässt.

Zunächst war die Komplexität des Algorithmus unbekannt. Kleine Probleminstanzen konnten gut gelöst werden, und zahlreiche Verbesserungen des Algorithmus als auch neue Ansätze wurden vorgestellt. Für größere Probleminstanzen erreichten die Algorithmen jedoch schnell die durch Rechenzeit und Speicherplatz gesetzten Grenzen. Insbesondere konnten Gröbnerbasen mit vielen Variablen nur selten berechnet werden. Dieses Verhalten ist unvermeidlich wie Mayr und Meyer zeigten. Sie konnten eine untere Schranke für den Platzbedarf des Wortproblems für Polynomideale herleiten, welche exponentiell in der Anzahl der Variablen ist. Da Gröbnerbasen verwendet werden können, um das Wortproblem für Polynomideale zu lösen, muss ihre Berechnung ebenfalls schwer sein.

Das Ziel unseres Projektes innerhalb des SPP1489 ist es, interessante Fälle zu finden, in denen das Wortproblem für Polynomideale beweisbar einfacher und somit in der Praxis besser handhabbar ist. Bisher haben wir neue und exakte Komplexitätsergebnisse für das Wortproblem für allgemeine Polynomideale erzielt. Diese hängen von der Dimension des Ideals ab. Ferner haben wir zahlreiche neue und substantiell verbesserte obere Schranken für Probleme mit Polynomidealen erzielt; diese beziehen sich auf radikale Binomideale.

GBiC PolyA