Engineering fortgeschrittener (Hyper)graph b-Matching Algorithmen

• Antragsteller: Professor Dr. Christian Schulz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 543787284

Das Projekt zielt darauf ab, hochskalierbare Algorithmen für das Hypergraph (b-)Matching Problem zu entwickeln. Wissenschaftler haben kürzlich das Konzept von Matchings in Graphen auf allgemeinere Probleme wie Matchings oder b-Matchings in Hypergraphen erweitert, was den Anwendungsbereich und die Herausforderungen erweitert hat. Während das Maximum-Matching-Problem in Graphen in polynomialer Zeit gelöst werden kann, ist es in Hypergraphen NP-vollständig. Dennoch sind in der Praxis schnelle und skalierbare Approximations- und exakte Algorithmen erforderlich, um große und komplexe Eingaben zu verarbeiten. Derzeit gibt es jedoch keine skalierbaren (parallelen) Algorithmen für das Hypergraphen b-Matching Problem. Das Ziel des Projekts ist es, hochskalierbare Algorithmen für eine Reihe von Hypergraphen (b-)Matching-Problemen zu entwickeln. Dabei wird insgeseondere die Parallelisierung der Algorithmen im Focus stehen. Die Algorithmen werden für bestehende Bibliotheken, Schnittstellen und Anwendungen bereitgestellt. Die resultierenden Algorithmen und Implementierungen werden robuster, flexibler und skalierbar für große parallele Maschinen und Anwendungsinstanzen, die viel größer sind als zuvor möglich. Die erfolgreichsten Implementierungen werden als benutzerfreundliche Open-Source-Software bereitgestellt.

• DFG-Verfahren: Sachbeihilfen