Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Asymptotically Optimal Assignments In Ordinal Evaluations of Proposals

 

Abdullah Atmaca
MSc.Student
Computer Engineering Department
Bilkent University

In ordinal evaluations of proposals, a set of n proposals is assigned to a set of referees with predetermined sets of choices and capacities of proposals in order to maximize the number of pairs of proposals reviewed by referees. In our work, the following variant of the problem is considered: Given a set of referees, each with a capacity to review k proposals, 1 < k < n, determine the minimum number of referees that can cover all pairs of proposals. Then we construct assignments that meets the lower bound determined. We prove that six referees are both necessary and sufficient when k = n/2. We further show that referees are necessary for any k, 2 < k < n, and present a number of algorithms, all leading to assignments with asymptotically minimum numbers of referees. These results are not only theoretically interesting but they also provide practical methods for forming cost-effective evaluation and peer review of proposals.

 

DATE: 16 March, 2009, Monday@ 15:40
PLACE: EA 409