Vienna Research Groups for Young Investigators Call 2018 - Information and Communication TechnologyVRG18-012

Structural and Algorithmic Aspects of Preference-based Problems in Social Choice


VRG leader:
Institution:
Proponent:
Stefan Szeider
Institution:
Status:
Laufend (01.10.2019 – 30.09.2027) 96 Monate
Fördersumme:
€ 1.599.620

 
Kurzzusammenfassung:

Im Fachgebiet „Computational Social Choice“ geht es um Entscheidungsprozesse: Wenn viele Personen gewisse Vorlieben haben, wie wählt man dann eine Lösung aus, die möglichst vielen Leuten möglichst gut passt? Wie verteilt man etwa Studierende gemäß ihrer Wünsche auf verschiedene Colleges? Oder wie kann ein Film-Streaming-Dienst passende Filmvorschläge aussuchen, basierend auf den Filmen, die eine bestimmte Person bisher gesehen hat? Das Problem bei diesen Aufgaben ist, dass es im schlimmsten Fall zeitlich nicht möglich ist, alle Varianten durchzuprobieren. Die Anzahl der Varianten steigt mit der Zahl der Personen (oder der vorzuschlagenden Filme) so rasch an, dass die Rechenzeit ins Astronomische steigen würde. Jiehua Chen entwickelt Strategien, dieses Problem zu lösen. Oft ist es gar nicht nötig, alle mathematisch möglichen Varianten auszuprobieren, weil man viele von vornherein ausschließen kann. Echte, realistische Daten haben eine gewisse Struktur – und wenn man Möglichkeiten findet, diese Struktur geschickt zu nutzen, kann man die Rechenzeit drastisch verkürzen. So lassen sich in überschaubarer Zeit sogar Aufgaben lösen, die in die Klasse der schwierigen „NP-Probleme“ fallen.

 

Wir nutzen Cookies auf unserer Website. Einige von ihnen sind technisch notwendig, während andere uns helfen, diese Website zu verbessern oder zusätzliche Funktionalitäten zur Verfügung zu stellen. Weitere Informationen