Rank Aggregation Problems Seminar

Event Details

Date:
15 February from 2:00 pm — 3:00 pm
Venue:
Building: 26, Room: 135, Clayton Seminar Room
Campus:
Clayton
Open to:
All
Cost:
Free
Categories:

Description:

Presenters:

Professor Franz J. Brandenburg - University of Passau

Abstract:

Who is the best tennis player in the world if just the grand slam tournaments are taken into account? This question is a special instance of comparing and ranking information, which is an important topic in social and information sciences, in sports and on the web. The objective is to measure the difference of the preferences and to compute a consensus ranking.

A common method is using Borda's rules, where individual ranks are mapped to points or scores. The winner is who has most points. From the computational point of view this is very efficient, since it only needs elementary arithmetic.

An alternative is counting mismatches or displacements and finding a compromise with the least number of disagreements or moves. These measures are commonly known as the Kendall-tau and the Spearman footrule distances.

Ranking problems are usualy based on complete information where every voter provides a total order of all items or candidates. We consider a generalization where the data is only partially ordered. For example, many players are unrelated by the results just from the grand slams, or there may be ties by different winners of the tournaments. We investigate the computatinal complexity of ranking problems. For example, when mismatches are taken into account, the optimal compromise can be computed in O(n logn) time for two voters, the complexity is open for three voters and it is NP-hard for four voters. However, for displacments there is a polynomial time algorithm. The complexity becomes much harder if ties are allowed or if there are partial orders. Then the problems are mostly NP-hard, and some are approximable and fixed parameter tractable.

Speaker biographies:

Prof Dr Franz Brandenberg holds a Doctorate and Habilitation in Informatics from the University of Bonn, and since 1983 has been Full Professor of Computer Science (Chair in Theoretical Computer Science) at the University of Passau in Germany. He has also served as Chairman (Dekan) and Dean (Studiendekan) of the Faculty of Mathematics and Computer Science at Passau. He has been on the program committee for most conferences in the Graph Drawing series, hosting one in 1995. Research interests include: formal languages, automata theory and complexity; algorithms; graph drawing; computational geometry; computer science in education.

Event Contact

Name
Kevin Korb
E-Mail
Kevin.Korb@monash.edu
Phone
990 55198
Organisation
Monash University