University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Colloquium of the Department and the PhD Program

title

Algorithmic aspects of ranking

speaker

Prof. Dr. Franz Brandenburg, University Passau
Passau, Germany

date & place

Wednesday, 26.07.2006, 16:15 h
Room C252

abstract

Ranking means an ordering of a set of items, based on preferences of individual voters. The roots for a mathematical investigation of the ranking problem go back to Borda (1781) and Condorcet (1785). Ranking occurs in many contexts, including sports, voting, business, personal management, and most recently the Internet. Who is the winner? What are the top items? This is not clear, since there are opposing interests and conflicts.

We consider algorithmic aspects of ranking. Many ranking problems turn out to be NP-hard, which means that they are hard to compute. Hence there is a need for good approximation algorithms and heuristics. These can be established via the feedback arc set problem. As an example, we apply our techniques to the last Bundesliga 05/06, when the teams are ranked according to the Champions League mode. Then Bayern will still remain the champion, but there are some surprising changes for other teams.