Spring 2007 Seminar Series

DATE: Thursday, April 12, 2007
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
Dorit S. Hochbaum

TITLE
Ranking Sports Teams, Web Pages, Academic Papers, NSF Proposals and More with Optimization Techniques

ABSTRACT
There are several leading techniques used for ranking. Notable among those are techniques relying on the principal eigenvector. We describe the rationale for using the principal eigenvector or the average weight method and point out some of the shortcomings of these techniques. We present alternative models that can address these shortcomings and offer a great deal of flexibility in the sources of information used. Our approach views the ranking problem as solving an inverse equal paths problem on a graph. We show that the problem can be solved in polynomial time using network flow techniques. The new model has a number of advantages including the ability to differentiate between sports games or web links based on some measure of significance. Furthermore, our algorithm for the problem, stated as a combinatorial graph problem, is more efficient than the principal eigenvector approach.

 

The paradigm presented has applications beyond rankings in data mining and pattern recognition.