Sublinearzeitalgorithmen

• Antragsteller: Professor Dr. Christian Sohler
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2008 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 93860940

Die Entwicklung von effizienten Algorithmen zur Analyse sehr großer Datenmengen hat sich zu einer zentralen Fragestellung in vielen Anwendungen der Informatik entwickelt. Häufig kann man die Daten augrund ihres Volumens nicht einmal auf Festplatten speichern. Dann sind selbst Linearzeitalgorithmen zu langsam, um die Eingabe effizient zu bearbeiten. Eine Methode, relevante Informationen zu extrahieren, bieten zufällige Stichproben. Ähnlich wie bei einer Wahlprognose versucht man durch eine geschickte Wahl der Stichprobe eine möglichst gute Repräsentation der Daten zu erreichen. Da hierbei nur ein kleiner Teil der gesamten Daten analysiert wird, spricht man auch von Sublinearzeitalgorithmen. Ziel diese Projektes ist die Weiterentwicklung von Sublinearzeitmethoden im Rahmen des Property Testing und von sublinearen Approximationsalgorithmen. Dabei wollen wir neue Algorithmen und Analysemethoden entwickeln, um Probleme in dünn besetzten Graphen (z.B. planaren Graphen) und geometrischen Graphen zu approximieren. Wir werden unseren Schwerpunkt auf repräsentative Probleme wie Matching, unabhängige Mengen, Knotenüberdeckung oder Travelling Salesman legen. Außerdem werden wir versuchen, Klassen von Problemen zu finden, die sublineare Approximationsalgorithmen besitzen.

• DFG-Verfahren: Sachbeihilfen