Colloquia

The Rank Aggregation Problem

David P. Williamson
Cornell University

December 5, 2007
Ricketts 211 - 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.

Abstract:

The rank aggregation problem was introduced by Dwork, Kumar, Naor, and Sivakumar (WWW 2001) in the context of finding good rankings of web pages by drawing on multiple input rankings from various search engines. The work draws on earlier work in the social choice literature on combining voter preferences specified by ranked alternatives. Dwork et al. propose finding a ranking that minimizes the sum of its Kendall distance to the input rankings; this can be viewed as a weighted feedback arc set problem. I will give an overview of the rank aggregation problem and some of its applications, including an application to intranet search (WWW 2003). I will also cover recent work done on finding good approximation algorithms for the problem. In particular, Ailon, Charikar, and Newman (STOC 2005) introduce a randomized ``pivoting'' algorithm for rank aggregation and related problems; recent work has extended this to deterministic pivoting algorithms for constrained versions of the problem (van Zuylen, Hegde, Jain and Williamson, SODA 2007, van Zuylen and Williamson 2007) and has yielded a polynomial-time approximation scheme for the problem (Kenyon-Mathieu and Schudy, STOC 2007). If time permits, I will discuss some extensions of this work to finding good clusterings and hierarchical clusterings.

Bio:

David Williamson was born in Madison, Wisconsin, but grew up in the suburbs of Honolulu, Hawaii. He received his Ph.D. in 1993 from the Massachusetts Institute of Technology. In 1995 he joined IBM Research, and from 2000-2003 was the Senior Manager of the Computer Science Principles and Methodologies Department at IBM's Almaden Research Center. In 2004, he joined Cornell University as a professor in the School of Operations Research and Information Engineering, and the Faculty of Computing and Information Science. David is well-known for his work on the topic of approximation algorithms. His Ph.D. dissertation on designing low-cost survivable networks was awarded several prizes, including the 1996 SIAM DiPrima Prize and the 1994 Tucker Prize from the Mathematical Programming Society. His work with Michel Goemans on the uses of semidefinite programming in approximation algorithms was awarded the 1999 SIAM Activity Group on Optimization prize, and the 2000 Fulkerson Prize from the Mathematical Programming Society and the American Mathematical Society. He serves as an associate editor on several journals, and is the Area Editor for Discrete Optimization on the journal Mathematics of Operations Research.

Hosted by: Elliot Anshelevich (x6491)

For more information:

Research Page

Last updated: November 1, 2007