W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Mathematics Colloquium talk
September 21, 2012
2pm - 3pm
We have the ability to gather enormous amounts of data, which gives rise to numerous challenges in organizing this data into usable information. One of the questions that arises is the question of how to combine information from different sources: for example, how do we combine recommendations to a user based on different criteria? How do we aggregate ranking functions in search engines? Can we get better search engines by combining the results of different algorithms?
These problems are instances of the rank aggregation problem, which has a long history in social choice and voting. In this talk, we consider the Kemeny rank aggregation problem, and we consider the problem from a computational point of view. Finding an optimal Kemeny ranking is NP-hard. However, we will show two algorithms that run in polynomial time, and we will prove that they find a solution that is close to optimal. The key ideas in our analysis can also be used to give provably good algorithms for certain problems where we want to organize data into clusters, for example clustering data based on similarity scores, and clustering genes based on microarray experiments.
These problems are instances of the rank aggregation problem, which has a long history in social choice and voting. In this talk, we consider the Kemeny rank aggregation problem, and we consider the problem from a computational point of view. Finding an optimal Kemeny ranking is NP-hard. However, we will show two algorithms that run in polynomial time, and we will prove that they find a solution that is close to optimal. The key ideas in our analysis can also be used to give provably good algorithms for certain problems where we want to organize data into clusters, for example clustering data based on similarity scores, and clustering genes based on microarray experiments.