Approximationsalgorithmen für geometrische Datenanalyse und ihre Anwendbarkeit

• Antragstellerin: Professorin Dr. Melanie Schmidt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 456558332

Geometrische Datenanalyse ist ein wachsendes Forschungsfeld, das auf der Schnittstelle zwischen Algorithmischer Geometrie und Maschinellem Lernen angesiedelt ist. Algorithmische Datenanalyse wird als Begriff für die Entwicklung von Datenanalysemethoden mit Techniken aus der Algorithmik, der Theorie und dem Algorithm Engineering etabliert. In diesem Projekt beschäftigen wir uns mit algorithmischer geometrischer Datenanalyse, oder, etwas präziser, mit Approximationsalgorithmen für geometrische Datenanalyseaufgaben. Der Fokus liegt auf der Entwicklung von Algorithmen mit beweisbaren Gütegarantien, und auf der Übertragung der Ergebnisse in praktisch effiziente Algorithmen. Wir interessieren uns auch für Nichtapproximierbarkeitsergebnisse, die die Grenzen des Erreichbaren abstecken.Datenanalyseaufgaben sind häufig schwierig zu lösen, beinhalten Nebenbedingungen oder eine komplizierte kombinatorische Struktur. Häufig werden sie daher mit Heuristiken bearbeitet. Heuristiken bieten keine Garantie bezüglich der Qualität der Lösung. Ist eine Qualitätsgarantie wichtig oder liefern Heuristiken erkennbar schlechte Lösungen, werden auch exakte Algorithmen verwendet, die häufig auf ganzzahligen linearen Programmen beruhen und mit verfügbarer Standardsoftware gelöst werden können. Dieser Ansatz benötigt jedoch im Allgemeinen exponentielle Laufzeit und ist auch in der Praxis häufig nicht schnell genug.Approximationsalgorithmen bieten eine Alternative. Sie besitzen eine theoretische Laufzeitschranke, die polynomiell ist, und eine beweisbare Gütegarantie für die Qualität der berechneten Lösung. Approximationsalgorithmen sind besonders geeignet für die Lösung von Datenanalyseaufgaben, wenn sie zusätzlich praktisch effizient sind und in der Praxis sehr gute Lösungen berechnen (in der Regel besser als ihre theoretische Garantie). Das Gebiet des Designs von praktisch verwendbaren Approximationsalgorithmen hat in letzter Zeit eine große Popularität erlangt.Die geometrischen Datenanalyseaufgaben, die wir in diesem Projekt untersuchen, stammen hauptsächlich aus dem Bereich der Clusteranalyse, mit einem Fokus auf dem sehr wichtigen k-means Problem. Für das k-means Problem verringert sich die Lücke zwischen Theorie und Praxis zur Zeit und es besteht eine realistische Chance, sie zu schließen. Abgesehen von k-means wollen wir andere Clusteranalyseaufgaben bearbeiten, aber auch Verbindungen zwischen Clusteranalyse und weiteren geometrischen Datenanalyseaufgaben untersuchen. Spannende Verbindungen gibt es zum Beispiel zwischen Clusteranalyse und der Analyse von Trajektorien sowie zwischen Clusteranalyse und geometrischen Netzwerkdesignproblemen. Unser Ziel ist es, den Stand der Forschung von Approximationsalgorithmen für geometrische Datenanalyseaufgaben aus Sicht der Theorie voranzutreiben, aber auch, praktisch effiziente Approximationsalgorithmen zu entwerfen, zu implementieren und zu testen.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen