Die Forschung am Lehrstuhl Algorithmen und Komplexität von Prof. Hans Jürgen Prömel schlägt eine Brücke zwischen Diskreter Mathematik und Theoretischer Informatik.
Für viele kombinatorische Optimierungsprobleme sind effiziente, exakte Algorithmen nicht bekannt bzw. können unter allgemein akzeptierten komplexitätstheoretischen Annahmen nicht existieren. Wir entwerfen, analysieren und implementieren daher Algorithmen, die eine optimale Lösung approximieren oder in verschiedener Weise den Zufall zu Hilfe nehmen. Die Untersuchung der dabei auftretenden diskreten Strukturen bildet einen eigenständigen Forschungsschwerpunkt am Lehrstuhl, wobei wir darüberhinaus auch rein mathematisch motivierten Fragestellungen nachgehen. Im Bereich der Bioinformatik befassen wir uns unter anderem mit der Anwendung von zufälligen diskreten Strukturen zur Modellierung von Ähnlichkeitsnetzwerken.
Schwerpunkte
Folgen sie den Links, um Kurzdarstellungen zu erhalten.- Approximationsalgorithmen, randomisierte Algorithmen und probabilistische Analyse
- Zufällige Strukturen, extremale Kombinatorik und Ramseytheorie
- Bioinformatik
- Planare Graphen
Laufende Projekte
- Analyse und Modellierung komplexer Netzwerke (im Rahmen des DFG-Forschungszentrums Matheon)
- Forschergruppe "Algorithmen, Struktur, Zufall"
- Graduiertenkolleg "Methoden für Diskrete Strukturen"
- Berliner Centrum für Genombasierte Bioinformatik (BCB)
- Berlin-Poznan Seminar in Diskreter Mathematik
Abgeschlossene Projekte
- DFG-Projekt "Approximative, randomisierte und probabilistische Algorithmen für kombinatorische Optimierungsprobleme"
- Graduiertenkolleg "Algorithmische Diskrete Mathematik"
- Europäisches Graduiertenkolleg "Combinatorics, Geometry, and Computation"
- DISSY (Stundenplanung im öffentlichen Nahverkehr)
- DFG-Projekt "Probabilistische Argumente und algorithmische Probleme in Graphen und Hypergraphen"
- PARALOR (Parallel Algorithms for Large Scale Operations Research Problems)
English