Von Algorithmen und Heiratsproblemen

Forscher der Hochschule Aalen gelingt Lösung eines berühmten Zuordnungsproblems der theoretischen Informatik

(PresseBox) - 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.

Weitere Infos zu dieser Pressemeldung:
Unternehmensinformation / Kurzprofil:
Bereitgestellt von Benutzer: PresseBox
Datum: 10.12.2019 - 13:38 Uhr
Sprache: Deutsch
News-ID 1778259
Anzahl Zeichen: 3428

Kontakt-Informationen:
Stadt:

Aalen

Kategorie:

Forschung und Entwicklung

Diese Pressemitteilung wurde bisher 338 mal aufgerufen.

An der Hochschule Aalen praxisnah und anwendungsorientiert Kunststoffe erleben ...
Kunststoffe stehen im Fokus der Medien, doch wie funktioniert Recycling eigentlich? Dieser Frage stellten sich jetzt 15 Schülerinnen und Schüler des Chemie-Leistungskurses des Aalener Theodor-Heuss-Gymnasiums gemeinsam mit ihrer Lehrerin Beate Ehret. Für eine umfassende Antwort ging’s an die Ho

Von Aalen in die Tiefsee und zurück ...
Wasser ist das Thema der Zukunft – davon ist Prof. Dr. Markus Glaser überzeugt. Egal ob Meerwasserentsalzung zur Trinkwassergenerierung, Energieerzeugung oder CO2-Speicherung, die Tiefsee bietet unzählige Anwendungsbereiche mit vielen spannenden Themen der Zukunft ab. Um realitätsnah Umgebungsb

Auswirkungen der Energiekrise auf Unternehmen: Welche Zukunftstechnologien zeigen Wirkung- ...
Die aktuelle Energiekrise stellt Unternehmen vor erhebliche Herausforderungen. In einem praxisbezogenen Klimasimulationsworkshop entwickelten Studierende der Masterstudiengänge Nachhaltige Unternehmensführung und Financial Management jetzt mithilfe des weltweit renommierten Klimasimulators En-ROAD

Weitere Mitteilungen von Hochschule Aalen - Technik und Wirtschaft

Papierlos arbeiten, digital punkten: Die neue Ära der Büroberufe ...
Der deutsche Arbeitsmarkt für Büro- und Verwaltungskräfte zeigt sich robust: Unternehmen suchen kontinuierlich nach qualifizierten Fachkräften - von Office Managern über Büroassistenzen bis hin zu Kaufleuten für Büromanagement. Diese stabile Nachfrage eröffnet Menschen in beruflichen Überg

Fraunhofer IGD - Fachkräftemangel in der Inneren Sicherheit als strukturelle Herausforderung ...
Steigende Anforderungen in der Inneren Sicherheit: Digitale Technologien unterstützen Sicherheitsbehörden Begrenzte personelle Ressourcen und komplexere Einsatzlagen erfordern neue Ansätze in der Inneren Sicherheit. Das Fraunhofer-Institut für Graphische Datenverarbeitung IGD zeigt, wie digit

Fraunhofer IGD - Fachkräftemangel in der Inneren Sicherheit als strukturelle Herausforderung ...
Begrenzte personelle Ressourcen und komplexere Einsatzlagen erfordern neue Ansätze in der Inneren Sicherheit. Das Fraunhofer-Institut für Graphische Datenverarbeitung IGD zeigt, wie digitale Technologien Ermittlungen effizienter gestalten und Einsatzkräfte bei Analyse und Entscheidungsfindung gez

IBB startet mit neuem Partner in die Zukunft - NORD Holding übernimmt Marktführer für berufliche Weiterbildung ...
Das Institut für Berufliche Bildung (IBB) steht für bewährte Qualität, hohe Kundenzufriedenheit und konsequente Innovationskraft. Mit einem breiten Angebot an zertifizierten Weiterbildungen und Umschulungen, ist das IBB ein verlässlicher Begleiter für Teilnehmende und Unternehmen gleichermaße

Fett für O-Ringe im Vakuumsystem: Cleveres Upgrade oder schlechte Idee ...
Eine Möglichkeit, die Dichtung zu optimieren, ist das Einfetten des O-Rings. Aber ist das eine gute Idee, oder könnte diese kleine Veränderung in der Vakuumanwendung am Ende mehr Probleme verursachen als lösen? Im Folgenden betrachten wir vier Gründe, warum das Einfetten eines O-Rings hilfreich

Mensch vs. Maschine: Warum KI den Job nicht gewinnt ...
Berlin, 2026 - In der Recruitingwelt ist Künstliche Intelligenz angekommen - und zwar auf beiden Seiten. Anna Müller (34) sitzt am Konferenztisch, ihr Laptop geöffnet, Bewerbungsunterlagen perfekt optimiert durch KI. Anschreiben, Lebenslauf, Schlüsselbegriffe - alles auf die ausgeschriebene Se

Interview: Serviceroboter in Hotellerie & Gastronomie ...
„Nicht die Anschaffung entscheidet – sondern die Integration in den Alltag.“Im Gespräch mit Bernd C. Strunk von GENESYS die kreativen Köpfe und Chanfang Wang von Genie InBot Bernd:Chanfang, viele Hotels und Restaurants beschäftigen sich aktuell mit Service- und Reinigungsrobotern. Viele gl

»Der Leadership Impact Code«: Führungswirkung messen als Grundlage gezielter Führungsentwicklung ...
Vlotho, 9. Mai 2026. Laut dem Gallup Engagement Index ist mangelnde Führungsqualität nach wie vor der entscheidende Treiber von Mitarbeiterfluktuation in deutschen Unternehmen. Gleichzeitig investieren Organisationen erheblich in Führungsentwicklung, ohne die tatsächliche Leadership-Wirkung syst

Europäischer Preis für nachhaltige Energie 2026: Deutsche Regulierungsexpertin Dr. Nadia Horstmann nominiert ...
(Brüssel/ Berlin) 5. Mai 2026 Dr. Nadia Horstmann, Regulierungsexpertin bei der Bundesnetzagentur, ist in der Kategorie "Frauen in Energie" für den Europäischen Preis für nachhaltige Energie 2026 nominiert. Die Gewinnerin unter drei Finalistinnen wird durch eine öffentliche Online-Ab

EdTech Talks 2026: Experteneinblicke in die digitale Bildungswelt ...
Leuphana Zertifikatsprogramm EdTech Product Management startet erneut Lüneburg. Mit der Online-Veranstaltungsreihe "EdTech Talks" startet an der Professional School der Leuphana Universität Lüneburg im Mai ein neues digitales Format rund um Innovationen und Zukunftsperspektiven im Bildu