Spannerprobleme und Mehrkriterialität

• Antragsteller: Professor Dr. Markus Chimani
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 517835933

Gegeben ein Graph $G$, ggf. mit Kantenlängen und Kantenkosten. Ein $\alpha$-Spanner ist ein Teilgraph von $G$ in dem die kürzesten Wege maximal um Faktor $\alpha$ länger sind als in $G$. Zumeist wird das Problem betrachtet, einen möglichst kleinen bzw. kostenminimalen Spanner für vorgegebenes $\alpha$ zu berechnen. Das Spannerproblem hat zahlreiche Anwendungen, in der Literatur existieren zahlreiche Forschungen, insb. aus dem Bereich der approximativen Algorithmen, und Spanneralgorithmen tauchen regelmäßig als intergraler Bestandteil in anderen Algorithmenresultaten auf. Dennoch sind Ergebnisse für Spanner in drei anderen Forschungsfeldern bisher sehr rar: (a) exakte Verfahren, (b) Algorithm Engineering (also insb. praktische und praxistaugliche Umsetzungen), und (c) mehrkriterielle Varianten des Problems (die in der Realitat tatsächlich recht typisch erscheinen). In unserem Projekt verknüpfen wir all diese drei Gebiete auf unterschiedliche Weise: 1) Wir betrachten exakte ILP-basierte Verfahren zum Lösen des klassischen Minimum $\alpha$-Spanner Problems, sowohl aus theoretisch-polyedrischer als auch aus praktischer Sicht. Dabei werden in einem Spaltengenerierungsverfahren Pricing-Probleme gelöst werden müssen, zu dem sich Algorithmen für mehrkriterielle kürzeste Wege auf natürliche Weise anbieten. 2) Wir betrachten verschiedene mehrkriterielle Varianten des Spanner-Problems (also z.B. zwei verschiedene Kostenfunktionen, Minimierung sowohl der Kosten als auch von $\alpha$, etc.). Statt einem optimalen Zielfunktionswert gilt es nun eine ganze Paretofront (bzw. deren Extrempunkte) zu berechnen. Dafür werden wir sowohl exakte als auch approximative Verfahren entwicklen und in der Praxis umsetzen.

• DFG-Verfahren: Sachbeihilfen