Computational Geometry: Solving Hard Optimization Problems (CG:SHOP)

• Antragsteller: Professor Dr. Sándor Fekete
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 444569951

In den über 40 Jahren seit den Anfängen der Algorithmischen Geometrie wurde bereits ein weites Spektrum an Optimierungsproblemen betrachtet, hauptsächlich aber aus der theoretischen Perspektive. Viele dieser Probleme gehören zur Klasse der NP-schweren Probleme, für die nicht mit der Existenz polynomieller Algorithmen zu rechnen ist. Obwohl viele derartige Probleme betrachtet wurden, bestehen positive Resultate typischerweise aus Methoden mit polynomieller Worst-Case-Laufzeit, die einen konstanten Approximationsfaktor liefern, nicht aber praktische Methoden, realistische Laufzeiten, oder gar exakte Verfahren, die beweisbar optimale Lösungen liefern. Prinzipiell ist dies eine Zielrichtung des relativ jungen Bereichs des Algorithms Engineering; allerdings ist der Einfluss auf die Algorithmische Geometrie bislang begrenzt, vor allem beim Lösen schwerer Optimierungsprobleme. Dies liegt auch an besonderen Schwierigkeiten geometrischer Probleme, erfordert also zusätzliche Anstrengungen. Unser Projekt zielt auf wichtige Fortschritte im Umgang mit diesen Schwierigkeiten, basierend auf Methoden aus der Kombinatorischen Optimierung in Kombination mit Algorithmischer Geometrie und Algorithm Engineering, bei ausgewiesener Expertise in allen drei Bereichen. Auf der konkreten Ebene werden wir eine Auswahl verschiedener, natürlicher geometrischer Optimierungsprobleme behandeln, die bereits von theoretischer Seite betrachtet wurden, für die aber bislang wenig praktische Verfahren existieren, die beweisbar optimale oder nahezu optimale Lösungen produzieren können. Für diese Probleme werden wir Lösungsverfahren und -ergebnisse produzieren, basierend auf Vergleichsinstanzen und Methoden, die als Richtwerte sowohl für konkrete Lösungen als auch für praktische Lösungsmethoden dienen können. Auf der allgemeinen Ebene werden wir generische Werkzeuge und Methoden für das Lösen geometrischer Optimierungsverfahren entwickeln, die praktische nützliche Ergebnisse liefern, indem wir Ausdünnungstechniken für große Instanzen anwenden, ebenso wie für den Umgang mit ungenauen Daten und Fehleranalyse. Insgesamt werden wir damit eine Plattform entwickeln, die eine Sammlung von Werkzeugen liefert, eine Bibliothek von Testinstanzen und Ergebnissen, bis hin zur Durchführung von Wettbewerben.In den letzten Monaten ist es uns gelungen, das Potential unseres Ansatzes zu demonstrieren: Es ist uns gelungen, einen jährlichen praktischen Wettbewerb im Bereich der Algorithmischen Geometrie zu etablieren und durchzuführen, basierend auf Optimierungsproblemen der genannten Art. Dies beweist die Chance, ein bislang rein theorieorientiertes Gebiet um praktische Relevanz für schwere Probleme zu erweitern.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Israel, USA
• Kooperationspartner: Professor Erik Demaine, Ph.D.; Professor Dr. Dan Halperin; Professor Joseph S. B. Mitchell, Ph.D.