Thank you, Dan and Bert.
Bert - Your approach provides a solution. However, it has the undesired
property of referees lumping together (I apologize that I did not state this as
a condition). In other words, it does not "mix" the referees in some random
fashion.
Dan - your approach attempts to have the desired properties, but is not
guaranteed to work. Here is a counterexample:
> set.seed(1234)
> a <- assignment(40,15,3)
> table(a)
a
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 7 12 7 4 10 8 6 8 13 7 7 11 3 7
Notice that the difference between maximum and minimum candidates for referees
is 13 - 3 = 10. Of course, I have to increase the # iters to get a better
solution, but for large K and R this may not converge at all.
Best regards,
Ravi
From: Ravi Varadhan
Sent: Wednesday, April 30, 2014 1:49 PM
To: r-help@r-project.org
Subject: A combinatorial assignment problem
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@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.
