English Intern
Lehrstuhl für Informatik I - Algorithmen und Komplexität

Forschung

Übersichtliches Zeichnen von Graphen

Graphen sind nicht nur ein häufiges Hilfsmittel beim Modellieren und Lösen von Problemen in der Informatik, sondern werden auch oft zur Visualisierung von Daten genutzt. Auch für Laien sind konkrete Zeichnungen von Graphen oft gut verständlich, da die Darstellung einer Verbindung oder eines Zusammenhangs durch Kanten intuitiv ist. Darüber hinaus lassen sich Methoden zum Zeichnen von Graphen auch oft für das Zeichnen realer Netzwerke, wie z.B. (U-)Bahnnetze, verwenden. Wir entwickeln und untersuchen Algorithmen für das übersichtliche Zeichnen von Graphen.

» mehr

Algorithmen für Geographische Informationssysteme

Ein Geographisches Informationssystem (GIS) dient der Erfassung, Verwaltung, Analyse und Präsentation geographischer Information. In diesen Aufgabengebieten ergeben sich algorithmische Probleme, die oft geometrischer Natur sind. Beispielsweise müssen Gebäudeumrisse aus Rohdaten (z.B. aus 3D Punktwolken, die mittels Laserscanning gewonnen wurden) generiert werden. Grundsätzlich werden Geodaten benötigt, deren Abstraktions- bzw. Detailgrad zur jeweiligen Anwendung (z.B. zur Städteplanung oder Klimamodellierung) passt. Daher sind Algorithmen zur automatischen Generalisierung erforderlich, welche einen Geodatensatz an einen höheren Abstraktions- bzw. niedrigeren Detailgrad anpassen können. Insbesondere wird die Generalisierung bei der kartographischen Visualisierung eingesetzt, um übersichtliche Landkarten zu erzeugen, wobei sie mit einer Reduktion des Kartenmaßstabs einhergeht.

» mehr

Kompetitive Standortprobleme

Wir untersuchen eine Klasse von Standortproblemen, bei denen zwei konkurrierende Anbieter ihre Versorger sequenziell platzieren, und die Kunden sich zwischen den Konkurrenten entscheiden können. Wir nehmen an, dass beide Konkurrenten nicht-kooperativ agieren und auf die Maximierung ihres eigenen Vorteils abzielen. Wir untersuchen die Komplexität und Approximierbarkeit solcher Probleme auf Graphen, insbesondere auf einfachen Graphklassen wie Bäumen und Pfaden. Ferner entwickeln wir schnelle Algorithmen für kompetitive Einzelstandortprobleme, bei denen jeder Anbieter genau einen Versorger errichtet.

» mehr

Komplexität und Automaten

Wir untersuchen Eigenschaften vollständiger Mengen von Komplexitätsklassen, z.B. die Redundanz NP-vollständiger Mengen. Man vermutet, dass alle NP-vollständigen Mengen hochgradig redundant sind, kann dies aber nicht allgemein zeigen. Daher sucht man nach schwächeren Redundanzaussagen, die sich für alle NP-vollständigen Mengen nachweisen lassen.

» mehr

Optimierung für den öffentlichen Verkehr

Hochfrequent, von Tür zu Tür, mit kurzen Reisezeit und robust gegen Störungen - so wünschen wir uns den öffentlichen Verkehr, damit er eine echte Alternative zum Auto darstellt. Neben diesen Qualitätsansprüchen wollen Verkehrsbetriebe natürlich auch Kosten und zunehmend auch Emissionen klein halten. 

Traditionell wird das Erstellen eines Verkehrsangebots in die Schritte Infrastrukturplanung, Linienplanung, Fahrplanung, Materialplanung, Personalplanung unterteilt.  Diese Planungsprobleme werden, teilweise basiert auf sehr vereinfachenden Annahmen, oft mit Hilfe von Netzwerken modelliert und mit Methoden der ganzzahligen linearen Optimierung gelöst.

Spannende Herausforderungen ergeben sich dort, wo vereinfachende Annahmen mit realistischeren ersetzt werden, zum Beispiel im Bereich Nachfragemodellierung oder Datenverfügbarkeit. Wir beschäftigen uns mit der Modellierung und Lösung solcher Optimierungsprobleme.