Home   Contact Research:   Events   Seminars People:   Faculty members   Graduate students   Postdoctoral fellows   Alumni   Postdoctoral positions Prospective Students:   Admission   Life at Waterloo   International Students

Algorithms and Complexity Seminar     Date: Wednesday, September 30, 2009 Time: 3:30 PM Place: MC5136         Title: Improved Parameterized Algorithms for the Kemeny Aggregation Problem Speaker: Narges Simjour, School of Computer Science, University of Waterloo Abstract:   We give improved fixed parameter tractable (FPT) algorithms to solve the Kemeny aggregation problem, where the task is to summarize a multi-set of preference lists, called votes, over a set of alternatives, called candidates, into a single preference list that has the minimum total tau-distance from the votes. The tau-distance between two preference lists is the number of pairs of candidates that are ordered differently in the two lists. We study the problem for preference lists that are total orders. We develop algorithms of running times O*(1.403^kt ), O*(5.823^{kt/m}) \leq O*(5.823^kavg) and O*(4.829^kmax) for the problem, ignoring the polynomial factors in the O* notation, where kt is the optimum total tau-distance, m is the number of votes, and kavg (resp, kmax ) is the average (resp, maximum) over pairwise tau-distances of votes. Our algorithms improve the best previously known running times of O*(1.53^kt) and O*(16^kavg)\leq O*(16^kmax), which also implies an O*(16^{4kt/m}) running time. We also show how to enumerate all optimal solutions in O*(36^{kt/m})\leq O*(36^kavg) time. This work was presented at IWPEC 2009.