KIT-Forscherteam gewinnt Algorithmenwettbewerb

Von Links: Johannes Fichte (Program Committee), Markus Hecher (Program Committee), Christian Schulz, Demian Hespe, Bart Jansen (Steering Committee Chair), Frances Rosamond (Steering Committee)

Ein Team aus der Arbeitsgruppe Algorithmik II  von Professor Sanders (ITI), bestehend aus Demian Hespe, Sebastian Lamm und zwei ehemaligen Kollegen, die inzwischen der Uni Wien und dem Hamilton College angehören, konnten die diesjährige "Parameterized Algorithms and Computational Experiments Challenge" (PACE) für sich entscheiden und damit erneut einen Sieg für das Institut für Theoretische Informatik (ITI) einfahren. 
Als Vertreter des Karlsruher Instituts für Technologie (KIT) belegte das Team mit seinen Berechnungen des "Vertex Cover" Problem den ersten Platz des Wettbewerbes, der mit einem Preisgeld von 750 Euro datiert war. Daneben wurden zwei weitere Probleme der „Hypertree Breite“ zur Aufgabe gestellt, die es ebenfalls zu lösen galt. Die Gewinner aller Kategorien wurden beim „International Symposium on Parameterized and Exact Computation“ (IPEC2019), das vom 11-13 September in München tagte, bekannt gegeben und ausgezeichnet. 

Im Wettbewerb galt es, Lösungen zu einem klassischen NP-schweren kombinatorischen Graphproblem anzubieten. Es handelt sich dabei um ein bewiesenermaßen schwer zu lösendes Problem, das mit sogenannten parametrisierten Algorithmen dennoch greifbar gemacht werden kann. Eins der meist untersuchten Beispiele ist dabei das Vertex Cover Problem. Die Teams sollten mit Hilfe von Berechnungen versuchen, die Vertex Cover in kleinstmöglicher Größe auszugeben. Gemessen wurde die Anzahl gelöster Instanzen, wobei das KIT-Team 87 Instanzen lösen konnte und damit vor den zweitplatzierten der University of Glasgow mit 77 Instanzen sowie den 22 weiteren teilnehmenden Teams lag. Die Platzierungen und Ergebnisse sind der Tabelle zu entnehmen: https://pacechallenge.org/2019/ 

Die vier Wissenschaftler haben sich bereits in der Vergangenheit mit Problemen dieser Art beschäftigt und konnten ihre Expertise daher gut einbringen und so einen passenden Algorithmus für den Wettbewerb schreiben. Dieser ist im Grunde eine Kombination aus bestehenden Algorithmen, die in verschiedenen Situationen unterschiedlich gut funktionieren. 

Seit 2015 findet die Parameterized Algorithms and Computational Experiments Challenge jährlich statt und macht sich zur Aufgabe, die Beziehung zwischen parametrisierten Algorithmen und der Praxis zu vertiefen. Themen aus multivariaten Algorithmen, exakten Algorithmen, feinkörniger Komplexität und verwandten Bereichen stehen dabei im Fokus. Ziel des PACE-Wettbewerbs ist es, die Anwendbarkeit der algorithmischen Ideen zu untersuchen. Das PACE-Format soll darüber hinaus zu neuen theoretischen Entwicklungen inspirieren. Die durch die zukunftsorientierte Ausrichtung gewonnenen Erkenntnisse können so in spätere Studien aufgenommen und weiterverarbeitet werden.

Weitere Informationen zum diesjährigen Wettbewerb unter https://pacechallenge.org