Von Algorithmen und Heiratsproblemen

Zuordnungsprobleme sind alltägliche Probleme, die jeder kennt. Wie soll die Tischordnung bei der betrieblichen Weihnachtsfeier aussehen? Oder wie lastet eine Firma ihre Maschinen mit den anstehenden Arbeiten am besten aus? Das sogenannte „Heiratsproblem“, im Fachjargon als „perfektes Matching-Problem“ bezeichnet, ist nicht nur ein besonders anschauliches und berühmtes Zuordnungsproblem aus der Informatik, es ist auch ein  zentrales Problem, mit Verbindungen zu vielen anderen Problemstellungen der Informatik. Unentbehrliches Handwerkszeug sind dabei Algorithmen. Diese können manchmal ein Problem mit Hilfe von Zufall effizient lösen. Denn immer dann, wenn es einen Suchbereich gibt, in dem sehr viele der gesuchten Lösungen vorkommen, kann ein Algorithmus zufällig einen oder mehrere Kandidaten auswählen. Mit hoher Wahrscheinlichkeit ist dann eine gesuchte Lösung dabei. Man spricht hierbei von einem randomisierten Algorithmus.

„Dieser wurde vor mehr als 30 Jahren entwickelt. Und seither fragen sich die Forscher weltweit, ob man für das perfekte Matching-Problem auch eine Lösung ohne Zufall effizient berechnen kann“, erklärt Prof. Dr. Thomas Thierauf, der an der Hochschule Aalen theoretische Informatik und Mathematik lehrt. Auch ihn selbst hat das knifflige, „aber sehr faszinierende Problem“ seit vielen Jahren beschäftigt. Jetzt haben er und seine Kollegen Stephen Fenner von der University of South Carolina (USA) und Rohit Gurjar vom Indian Institute of Technology Bombay (Indien) den Durchbruch geschafft und eine Lösung gefunden, die viel Aufsehen erregt hat. Die richtungsweisende Lösung, die laut Thierauf „in den Tiefen der Algebra, Geometrie und Kombinatorik liegt“, wurde auf einer der beiden weltweit renommiertesten Konferenzen für theoretische Informatik vorgestellt und in der amerikanischen Fachzeitschrift CACM als Research Highlight veröffentlicht.

Die Rubrik CACM Research Highlights widmet sich den wichtigsten aktuellen Forschungsergebnissen, die in der Informatik veröffentlicht wurden. In der Regel erscheint nur ein Artikel pro Monat. Das Paper „A Deterministic Parallel Algorithm for Bipartite Perfect Matching“ von Prof. Dr. Thomas Thierauf und seinen Kollegen Stephen Fenner und Rohit Gurjar, der als Postdoc auch an der Hochschule Aalen geforscht hat, wurde für die Rubrik Research Highlights ausgewählt. „Es ist wirklich klasse, dass wir in dieser Rubrik erscheinen, denn in Informatiker-Kreisen gilt das als bedeutende Auszeichnung“, freut sich Thierauf.