Betzler, NadjaHölldobler, Steffen2020-08-212020-08-212011978-3-88579-415-8https://dl.gi.de/handle/20.500.12116/33787Die Dissertation "A Multivariate Complexity Analysis of Voting Problems" befasst sich mit NP-harten Problemen im Kontext von Wahlen. Das Ziel ist mittels Methoden der parametrisierten Algorithmik ein besseres Verständnis der kombinatorischen Schwierigkeit dieser Probleme zu erlangen und dabei relevante Szenarien zu identifizieren, in denen diese "tractable", das heißt effizient lösbar, sind. Die betrachteten Probleme umfassen die Berechnung eines Gewinners sowie die Erstellung einer Konsensrangliste. Desweiteren wird die Frage nach einem Möglichen Gewinner im Falle von unvollständiger Information sowie die Beeinflussung eines Wahlausgangs durch Löschen oder Hinzufügen von Kandidaten untersucht. Der Schwerpunkt liegt auf einer theoretischen Analyse. Für das sogenannte RANK AGGREGATION-Problem werden einige der entwickelten Algorithmen auch experimentell evaluiert.de1617-5468