Engineering of Matching and Covering Algorithms in Large Graphs and Hypergraphs

• Applicant: Professor Dr. Anand Srivastav
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering