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.