[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