Von Algorithmen und Heiratsproblemen
ID: 1778259
Forscher der Hochschule Aalen gelingt Lösung eines berühmten Zuordnungsproblems der theoretischen Informatik
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:
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 364 mal aufgerufen.
Die Pressemitteilung mit dem Titel:
"Von Algorithmen und Heiratsproblemen"
steht unter der journalistisch-redaktionellen Verantwortung von
Hochschule Aalen - Technik und Wirtschaft (Nachricht senden)
Beachten Sie bitte die weiteren Informationen zum Haftungsauschluß (gemäß TMG - TeleMedianGesetz) und dem Datenschutz (gemäß der DSGVO).
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
Classic Minerals erbohrt bis zu 39,2 Gramm Gold pro Tonne auf Kat Gap ...
Ermutigende Bohrergebnisse legt heute der australische Goldexplorer Classic Minerals (WKN A0NA2L / ASX CLZ) von seinen Liegenschaften in Western Australia vor. Die neueste Runde an Bohrungen erbrachte bis zu 39,20 Gramm Gold pro Tonne. Classic stellte im Rahmen des aktuellen Bohrprogramms 21 Bohrung
Hamburger Headhunter mit erfolgreicher Rekrutierung von Geschäftsführern und Managementkräften ? Schwerpunkt Leitung Kaufmännischer Bereich ...
Die Hamburger Personalberater sind anerkannte Experten bei der Neubesetzung von Leitungsstellen. Die vergangenen sechs Monate bestätigen die professionelle und seriöse Arbeit der Karriereberater: Alle Mandate ? zum Teil große Suchaufträge mit Assessmentcenter, Definierung der Auswahlkriterien un
Grünenthal ernennt Jan Adams zum Chief Scientific Officer (FOTO) ...
Grünenthal hat heute bekannt gegeben, dass Dr. med. Jan Adams mit Wirkung zum 1. Januar 2020 zum Chief Scientific Officer (CSO) und zum Mitglied der Konzerngeschäftsführung ernannt worden ist. Seit Juli hat Jan Adams die Aufgaben des CSO bereits kommissarisch wahrgenommen und dabei die strategi
Beim Altern lässt die Spannung nach: Neuer mehrkanaliger Prüfstand erfasst Gummialterung ...
Die Eigenschaften von gummiähnlichen Kunststoffen ändern sich durch Temperatur- und Krafteinwirkung im Verlauf ihrer Nutzung. Für die Produktentwicklung, etwa von Fahrzeugreifen und Förderbändern an Supermarktkassen, ist es deshalb wichtig, Aussagen über die Lebensdauer dieser Elastomere unter
