Ranking Probleme bei unvollständiger Information

• Antragsteller: Professor Dr. Franz Josef Brandenburg
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2012 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 210423731

Das Internet hat der Theorie der Wahlsystemforschung neue Anwendungen und Impulse gebracht. Die Daten auf eine Anfrage werden von verschiedenen Suchmaschinen in unterschiedlicher Reihenfolge geliefert. Wähler beurteilen Kandidaten oder Elemente nach persönlichen Kriterien und Prioritäten und kommen zu unterschiedlichen Ergebnissen. Beim Ranking Problem geht es darum, aus diesen unterschiedlichen Reihenfolgen eine faire Gesamtlösung zu berechnen. Diese Thematik hat viele weitere Anwendungen u.a. im Sport und in der Sozialforschung.Gegenstand des Vorhabens ist eine algorithmische Untersuchung von Ranking Problemen bei unterschiedlichen Distanzmaßen mit dem Schwerpunkt auf unvollständiger Information. Die Unvollständigkeit ergibt sich aus Unentschieden zwischen Elementen (ist egal) über Unvergleichbarkeit (Äpfel und Birnen) bis hin zu Widersprüchen. Die Bewertung erfolgt durch Distanzmaße, die Nicht-Übereinstimmungen erfassen. Welchen Einfluss hat der Grad der Unvollständigkeit auf die Komplexität von Ranking Problemen? Wo gibt es die Sprünge in der Komplexität von polynomial zu NP oder von NP in die Polynomiale Hierarchie. Zur Beantwortung dieser Fragen sind die Ranking Probleme bezüglich ihrer Komplexität zu klassifizieren. Für die meist NP-harten Probleme sollen Approximationen entwickelt, Lösungen im Rahmen der Fixed Parameter Komplexität gesucht und effektive Heuristiken entworfen und algorithmisch bewertet werden.

• DFG-Verfahren: Sachbeihilfen