Project Details
Projekt
Approximationsalgorithmen für Clustering, Aggregation und Vereinfachung unter Nebenbedingungen
Antragstellerin
Professorin Dr. Melanie Schmidt
Subject Area
Theoretische Informatik
Term
since 2022
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 459420781
Dieses Projekt beschäftigt sich mit Nebenbedingungen im Kontext von Clustering-, Aggregations- und Vereinfachungsproblemen aus der Geodäsie, und mit der Frage, ob und wie es möglich ist, effizient approximative Lösungen für Probleme mit Nebenbedingungen zu finden. Nebenbedingungen entstehen sowohl bei der Erstellung von digitalen Karten als auch bei der Analyse von Meereshöhenmessungen. Clusteringprobleme, die auch in der Kombinatorik viel untersucht werden, sind häufig selbst ohne Nebenbedinungen NP-schwer, d.h. wahrscheinlich nicht in polynomieller Zeit optimal lösbar. Typische Lösungen in der Praxis sind die Verwendung von ILP-Formulierungen sowie von Beschleunigungstechniken für exakte Exponentialzeitalgorithmen oder der Entwurf von anwendungsspezifischen Heuristiken. Eine Alternative bieten Approximationsalgorithmen: Diese finden in polynomieller Zeit zwar keine optimale Lösung, aber eine Lösung, die eine approximative Gütegarantie erfüllt. Für klassische Clusteringprobleme existieren etliche Approximationsalgorithmen. Auch wenn Clustering- und Aggregationsprobleme, die in der Geodäsie auftreten, mit klassischen Clusteringproblemen verwandt sind, so unterscheiden sie sich doch in wichtigen Punkten: a) Sie enthalten sehr viele Nebenbedingungen und b) sie erwarten als Eingabeobjekte komplexe geometrische Objekte wie Polygone, Graphen oder Zeitreihen. In diesem Projekt zielen wir darauf ab, den Stand der Forschung für Clustering, Aggregation und Vereinfachung komplexer geometrischer Objekte unter Nebenbedingungen voranzutreiben.
DFG Programme
Forschungsgruppen
