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

Das Ziel unseres Projekts CG:SHOP (Computational Geometry: Solving Hard Optimization Problems) ist es, praktisch nutzbare Methoden zur Lösung schwerer geometrischer Optimierungsprobleme zu entwickeln. Dies basiert auf der grundlegenden Einsicht, dass die ausschließliche Konzentration auf die theoretische Komplexität einen wichtigen Punkt übersieht: Die Existenz von Algorithmen, deren asymptotische Laufzeit im Worst Case durch ein Polynom begrenzt ist, ist weder ausreichend noch notwendig, um praktisch nützliche Lösungen zu berechnen, die beweisbar optimal oder nahezu optimal sind. Zu diesem Zweck entwickeln wir Methoden, die theoretische Ansätze aus der Computational Geometry und der mathematischen Optimierung mit praktischen Techniken aus dem Algorithm Engineering verbinden, um beweisbar gute Lösungen für Instanzen von praktisch interessanter Größe für schwierige Probleme von praktischer Relevanz zu erhalten. Insbesondere haben wir eine Reihe spezifischer geometrischer Optimierungsprobleme betrachtet, die sich mit (A) Überdeckung und Dispersion, (B) Strukturproblemen und (C) Touring-Problemen befassen, sowie allgemeinere Aspekte von (D) Ausdünnungstechniken, (E) Fehlern und Zielfunktionen und (F) Toolbox und Bibliothek. Die erste Phase unseres Projekts war ein durchschlagender Erfolg, der bereits zu 15 Veröffentlichungen geführt hat, die alle Aspekte unseres ehrgeizigen Arbeitsprogramms abdecken, mit 4 weiteren in Begutachtung und 2 weiteren in Vorbereitung. Darüber hinaus ist es uns gelungen, auf dem weltweit führenden Symposium on Computational Geometry (SoCG) einen speziellen Track („The CG:SHOP Challenge“) einzurichten, der sich mit der praktischen Lösung von geometrischen Optimierungsproblemen befasst. Dies hat zu 25 weiteren Veröffentlichungen geführt, und mehrere weitere sind in Vorbereitung. Dieser Erfolg macht es möglich und wünschenswert, unsere Arbeit zu erweitern und zu verfeinern. Wie bisher werden wir eine Reihe spezifischer Problembereiche in den Bereichen (G) Fortgeschrittene Strukturprobleme, (H) Fortgeschrittene Touring-Probleme, (I) Pack-Probleme untersuchen, sowie allgemeinere Methoden und Perspektiven in den Bereichen (J) Analyse von Nachbarschaftsstrukturen, (K) Instanzraumanalyse und KI und (L) Herausforderungen und Gemeinschaftsbildung verfolgen.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Israel, USA
• Kooperationspartnerinnen / Kooperationspartner: Professor Dr. Aaron T. Becker; Professorin Dr. Erin Chambers; Professor Dr. Dan Halperin; Professor Dr. Joseph S. B. Mitchell