Logo des Repositoriums
 
Textdokument

Eine Multivariate Komplexitätsanalyse von Wahlproblemen

Vorschaubild

Volltext URI

Dokumententyp

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.

Beschreibung

Betzler, Nadja (2011): Eine Multivariate Komplexitätsanalyse von Wahlproblemen. Ausgezeichnete Informatikdissertationen 2010. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-415-8. pp. 31-40

Schlagwörter

Zitierform

DOI

Tags