Textdokument
Eine Multivariate Komplexitätsanalyse von Wahlproblemen
Lade...
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
2011
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Die 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.