UWA Logo
  Faculty Home | School Home | Internal Page | Awesome Animations   
           
Home
About the School
Contact and People
Future Undergraduate Students
Prospective Postgraduates
Current Students
Current Postgraduates
Research
Research Areas Research Areas Research Areas
Research Seminars Research Seminars Research Seminars
20092009 2009 2009
20082008 2008 2008
20072007 2007 2007
160320071603200716032007 16032007 16032007
040520070405200704052007 04052007 04052007
300520073005200730052007 30052007 30052007
240520072405200724052007 24052007 24052007
190620071906200719062007 19062007 19062007
090720070907200709072007 09072007 09072007
260720072607200726072007 26072007 26072007
06082007-Series06082007-Series06082007-Series 06082007-Series 06082007-Series
050720070507200705072007 05072007 05072007
17082007a17082007a17082007a 17082007a 17082007a
300720073007200730072007 30072007 30072007
17082007b17082007b17082007b 17082007b 17082007b
14092007a14092007a14092007a 14092007a 14092007a
14092007b14092007b14092007b 14092007b 14092007b
14092007c14092007c14092007c 14092007c 14092007c
191020071910200719102007 19102007 19102007
300820073008200730082007 30082007 30082007
191020071910200719102007 19102007 19102007
091120070911200709112007 09112007 09112007
071220070712200707122007 07122007 07122007
20062006 2006 2006
20052005 2005 2005
20042004 2004 2004
20032003 2003 2003
20022002 2002 2002
20012001 2001 2001
20002000 2000 2000
19991999 1999 1999
19981998 1998 1998
School Research Conferences School Research Conferences School Conferences
Tech Reports Tech Reports Tech Reports
Distinguished Visitors Distinguished Visitors Distinguished Visitors
Research Opportunities for Students Research Opportunities for Students Research Opportunities ...
Research Project Suggestions Research Project Suggestions Research Project Sugges...
IT News
Awards
Industry Links and Prizes
School and IT Information
Other
Internal Information

Seminar Series

Algorithmic Aspects of Ranking


Professor Dr Franz J Brandenburg
University of Passau, Passau, Germany
Wednesday, November 7, 11 am

Abstract



The ranking problem is computing a permutation of a list of items, which best expresses the preferences of a collection of voters. If two voters disagree on a pair of items this induces a conflict. The goal of the ranking problem is to minimize the number of disagreements. The ranking problem dates back to the 18th century when voting systems where introduced, and has regained interest by web applications.

We translate the ranking problem into a crossing minimization problem on multi-colored graphs, and then discuss the complexity of the ranking problem.

The ranking problem is NP-hard, even for four voters, and can be approximated within a factor of two. The determination of the winner seems harder than NP.
Top of Page