[R] A combinatorial assignment problem

[Bert Gunter]

I had  trouble with my email and it went before it should. Here's the
solution I meant to send:

Arrange the r referees in a circle.

start <- 0
Replicate k times{
end <- (start + m-1)%% r
output: c(start,end) +1
start <- (end+1)%% r
}


The start and end pairs give the subsets of referees around the
circle. The distributes the referees to the candidates as evenly as
possible. I leave it to you to translate this into code. It should be
very fast as no combinatorics are required.


-- Bert

Bert Gunter
Genentech Nonclinical Biostatistics
(650) 467-7374

"Data is not information. Information is not knowledge. And knowledge
is certainly not wisdom."
H. Gilbert Welch


> On Wed, Apr 30, 2014 at 10:48 AM, Ravi Varadhan <ravi.varadhan at jhu.edu> wrote:
>> Hi,
>>
>> I have this problem:  K candidates apply for a job.  There are R referees available to review their resumes and provide feedback.  Suppose that we would like M referees to review each candidate (M < R).  How would I assign candidates to referees (or, conversely, referees to candidates)?  There are two important cases:  (a) K > (R choose M) and (b) K < (R chooses M).
>>
>> Case (a) actually reduces to case (b), so we only have to consider case (b).  Without any other constraints, the problem is quite easy to solve.  Here is an example that shows this.
>>
>> require(gtools)
>> set.seed(12345)
>> K <- 10  # number of candidates
>> R <- 7    # number of referees
>> M <- 3   # overlap, number of referees reviewing  each candidate
>>
>> allcombs <- combinations(R, M, set=TRUE, repeats.allowed=FALSE)
>> assignment <- allcombs[sample(1:nrow(allcombs), size=K, replace=FALSE), ]
>> assignment
>>> assignment
>>       [,1] [,2] [,3]
>> [1,]    3    4    5
>> [2,]    3    5    7
>> [3,]    5    6    7
>> [4,]    3    5    6
>> [5,]    1    6    7
>> [6,]    1    2    7
>> [7,]    1    4    5
>> [8,]    3    6    7
>> [9,]    2    4    5
>> [10,]    4    5    7
>>>
>>
>> Here each row stands for a candidate and the column stands for the referees who review that candidate.
>>
>> Of course, there are some constraints that make the assignment challenging.  We would like to have an even distribution of the number of candidates reviewed by each referee.  For example, the above code produces an assignment where referee #2 gets only 2 candidates and referee #5 gets 7 candidates.  We would like to avoid such uneven assignments.
>>
>>> table(assignment)
>> assignment
>> 1 2 3 4 5 6 7
>> 3 2 4 4 7 4 6
>>>
>>
>> Note that in this example there are 35 possible triplets of referees and 10 candidates.  Therefore, a perfectly even assignment is not possible.
>>
>> I tried some obvious, greedy search methods but they are not guaranteed to work.   Any hints or suggestions would be greatly appreciated.
>>
>> Best,
>> Ravi
>>
>>
>>         [[alternative HTML version deleted]]
>>
>> ______________________________________________
>> R-help at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.