Engineering von Matching- und Überdeckungsalgorithmen in großen Graphen und Hypergraphen

• Antragsteller: Professor Dr. Anand Srivastav
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 47756257

Approximationsalgorithmen für Probleme in Hypergraphen und Graphen haben in den letzten 20 Jahren in der kombinatorischen Optimierung zu einem beispiellosen theoretischen Fortschritt geführt. Im Kontrast hierzu fehlten Implementierungen oder gar experimentelle Studien weitgehend. Gleichzeitig stagnierte auch der theoretische Fortschritt, insbesondere die Verbesserung der Approximationsgüten bei wichtigen Problemen wie Matching und Überdeckung in Hypergraphen. In dem hier zur Fortsetzung vorgelegten Projekt gelang es in der ersten Phase, diesbezüglich erste Fortschritte zu erzielen und neue Approximationsalgorithmen für Matching und Überdeckung in Hypergraphen zu entwerfen und partiell zu analysieren. Die Matchingalgorithmen wurden mit den Methoden des Algorithm-Engineering (AE) entworfen und experimentell studiert. Die Ziele in der zweiten Phase sind die analytische und statistische Fundierung der vermuteten Approximationsgüten, die Ausdehnung der experimentellen Basis, darauf basierend das Engineering von Algorithmen für das Knotenüberdeckungsproblem für Hypergraphen und von Streaming-Algorithmen für das Matchingproblem in großen Graphen, sowie deren effiziente Parallelisierung. Hierzu sollen verschiedene Methoden des Algorithmenentwurfes, wie Randomisierung, Derandomisierung und Approximation im Kontext des Algorithm-Engineering angewandt oder weiterentwickelt werden.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering