Von Algorithmen und Heiratsproblemen

Zehn Frauen, zehn Männer auf der Suche nach der idealen Partnerschaft. Gibt es ein Verfahren, mit der sich immer eine passende Konstellation findet, so dass alle glücklich sind? Das „Heiratsproblem“ ist ein Zuordnungsproblem aus der Mathematik und Informatik, das Wissenschaftler seit mehr als 100 Jahren beschäftigt. Bisher wurde sozusagen mit „Kommissar Zufall“ gearbeitet, doch jetzt ist es Prof. Dr. Thomas Thierauf von der Hochschule Aalen und seinen Kollegen Stephen Fenner und Rohit Gurjar gelungen, eine effiziente Lösung des Problems ohne Zufall zu finden. Ihr Paper hat in der Fachwelt viel Aufsehen erregt und wurde jetzt in der renommierten amerikanischen Fachzeitschrift Communication of the Association for Computing Machinery (CACM) publiziert.

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.

Firmenkontakt und Herausgeber der Meldung:

Hochschule Aalen – Technik und Wirtschaft
Beethovenstr. 1
73430 Aalen
Telefon: +49 (7361) 576-0
Telefax: +49 (7361) 576-2250
http://www.htw-aalen.de

Ansprechpartner:
Saskia Stüven-Kazi
Kommunikation / Presse- und Öffentlichkeitsarbeit
Telefon: +49 (7361) 576-1056
Fax: +49 (7361) 576-1057
E-Mail: kommunikation@hs-aalen.de
Für die oben stehende Pressemitteilung ist allein der jeweils angegebene Herausgeber (siehe Firmenkontakt oben) verantwortlich. Dieser ist in der Regel auch Urheber des Pressetextes, sowie der angehängten Bild-, Ton-, Video-, Medien- und Informationsmaterialien. Die United News Network GmbH übernimmt keine Haftung für die Korrektheit oder Vollständigkeit der dargestellten Meldung. Auch bei Übertragungsfehlern oder anderen Störungen haftet sie nur im Fall von Vorsatz oder grober Fahrlässigkeit. Die Nutzung von hier archivierten Informationen zur Eigeninformation und redaktionellen Weiterverarbeitung ist in der Regel kostenfrei. Bitte klären Sie vor einer Weiterverwendung urheberrechtliche Fragen mit dem angegebenen Herausgeber. Eine systematische Speicherung dieser Daten sowie die Verwendung auch von Teilen dieses Datenbankwerks sind nur mit schriftlicher Genehmigung durch die United News Network GmbH gestattet.

counterpixel