[R] A combinatorial assignment problem

[Daniel Nordlund]

> -----Original Message-----
> From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org]
> On Behalf Of Ravi Varadhan
> Sent: Wednesday, April 30, 2014 10:49 AM
> To: r-help at r-project.org
> Subject: [R] 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
> 

Well, if you don't need clever, a brute force approach could work (depending on the values of k, r, and m).  Something like this 


assignment <- function(k,r,m,max_iter=120) {
   n <- 0
   cmb <- combn(r,m)
   repeat {
     n <- n+1 
     tbl <- table(map<-cmb[,sample(1:choose(r,m),k)])
     if(min(tbl) == max(tbl)-1) break
     if(n > max_iter) break
   }
   return(t(map))
}
a <- assignment(10,7,3)


Dan

Daniel Nordlund
Bothell, WA USA