Ben Strasser belegt mit dem FlowCutter-Algorithmus ersten Platz im internationalen PACE-Wettbewerb

Am 24. August wurden im Rahmen der ALGO 2016 in Aarhus in Dänemark die Gewinner des ersten PACE Wettbewerbs (Parameterized Algorithms and Computational Experiments challenge) bekannt gegeben.
Als Vertreter des Karlsruher Instituts für Technologie (KIT) schaffte es Ben Strasser mit seinem „FlowCutter“-Algorithmus gleich zweimal aufs Siegertreppchen: In der Kategorie „Computing treewidth heuristically with a sequential algorithm“ belegte er den ersten Platz sowie den zweiten Platz in der Kategorie „Computing treewidth heuristically with a parallel algorithm“.

Bis zum 1. August konnten die Bewerber ihre Implementierungen zu einem der beiden im Wettbewerb vorgegebenen Tracks (Track A: Treewidth oder Track B: Feedback Vertex Set) einreichen. Für Track A gab es Einreichungen von insgesamt zehn Universitäten weltweit. Die Teilnehmer konnten sich hier in vier Kategorien zu Berechnungen von Baumweiten beweisen, wobei Ben Strasser sich der Herausforderung der Berechnung heuristischer Baumweiten stellte. Mit dem an der Forschungsgruppe Algorithmen I unter der Leitung von Professor Dorothea Wagner entwickelten FlowCutter-Algorithmus gelang es ihm innerhalb des vorgegebenen Zeitlimits von 100 Sekunden eine geeignete sequentielle und parallele Baumzerlegung zu berechnen. FlowCutter wurde ursprünglich zur Berechnung kleiner balancierter Schnitte in großen Straßengraphen entwickelt. Nun hat sich herausgestellt, dass der Algorithmus auch in anderen Gebieten nützlich ist.

Ziel des PACE-Wettbewerbs ist es, die Anwendbarkeit der algorithmischen Ideen zu untersuchen, die in den Teilgebieten der parametrisierten (fixed-parameter tractable) Algorithmen entwickelt wurden. Das Gebiet der parametrisierten Algorithmik beschäftigt sich mit dem Entwurf von effizienten Algorithmen für schwere Probleme. Der verfolgte Ansatz besteht darin anzunehmen, dass ein Eingabeparameter klein ist und zu zeigen, dass die Algorithmen unter dieser Voraussetzung effizient sind. Ein häufig verwendeter Eingabeparameter ist die sogenannte Baumbreite. Eine zentrale Frage, der sich der PACE-Wettbewerb widmet, ist wie sich die Baumbreite in der Praxis ausrechnen lässt, um die Brücke zwischen theoretisch effizienten parametrisierten Algorithmen und realer Anwendbarkeit zu schlagen.

Das PACE-Format soll darüberhinaus zu neuen theoretischen Entwicklungen inspirieren. Die durch die zukunftsorientierte Ausrichtung gewonnenen Erkenntnisse können so in spätere Studien aufgenommen und weiter verarbeitet werden.

Infos und Ergebnisse zum PACE-Wettbewerb hier.