[R] A combinatorial assignment problem
Charles Berry
ccberry at ucsd.edu
Thu May 1 18:16:13 CEST 2014
Ravi Varadhan <ravi.varadhan <at> jhu.edu> writes:
>
> 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
> >
>
Isn't this the problem of constructing a balanced incomplete block design?
The problem and an R package to handle it are described here:
http://www.r-bloggers.com/generating-balanced-incomplete-block-designs-bibd/
As noted there, you cannot always get balance.
A Google Scholar search on "balanced incomplete block design" will
pop up many classical works on this problem.
Maybe try the ExperimentalDesigns Task view.
HTH,
Chuck
More information about the R-help
mailing list