“Novel distance measures for rank aggregation A joint work with Farzad Farnoud, UIUC”

Dr. Olgica Milenkovic, Dept ECE, University of Illinois Urbana- Champaign

Wednesday, November 16, 2011 - 10:00am - 12:00pm

Core Building Lecture Hall


Rank aggregation is the problem of combining multiple candidate rankings into one list that best reflects the candidates' standing as a whole. Rank aggregation has many applications, in fields as diverse as bioinformatics, coding theory and social sciences.

Mathematically, the rank aggregation problem can be formulated as finding a permutation that represents the ``centroid'' of a set of permutations - i.e., a permutation that minimizes a given average distance function from the given set of permutations. The main issue arising in such aggregation problems is to identify distance functions that are scalable, flexible and easy to compute.
So far, no solutions that have these desirable properties were proposed.

We introduce a new class of cost-constrained permutation metrics that can be approximated within a constant in polynomial time. The cost functions are based on average transposition distances and for costs that have a tree-metric form, the presented algorithms are exact. To prove the optimality of the distance computation procedure, we use Menger's theorem and graphical representations of permutations.

We conclude the talk by describing a number of applications of the novel distance metric in ``collaborative rank aggregation'' and coding for multilevel flash memories.


Olgica Milenkovic received a MSc degree in mathematics and PhD degree in electrical engineering from the University of Michigan, Ann Arbor, in 2001 and 2002, respectively. From 2002 until 2006 she was with the faculty of University of Colorado, Boulder. In 2006, she was a visiting professor at the University of California, San Diego Center for Information Theory and Application. In 2007, she joined University of Illinois, Urbana-Champaign were she currently holds the position of associate professor. Her research interests are in algorithms, bioinformatics, coding theory, combinatorics and signal processing.

Olgica Milenkovic is a recipient of the NSF Career Award, the DARPA Young Faculty Award and a number of best conference paper awards. She currently serves as Associate editor in the Transactions on Signal Processing and the Transactions on Information Theory.