[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 Daniel Nordlund
> Sent: Thursday, May 01, 2014 1:10 AM
> To: r-help at r-project.org
> Subject: Re: [R] A combinatorial assignment problem
> 
> > -----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
> 
> 

I apologize for the noise.  I made some last second edits and cut and pasted the wrong code in the first email.  Obviously, you would want to add some error checking to the code to trap incompatible parameter specification.


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((max(tbl)-min(tbl)) <= 1) break
     if(n > max_iter) break
   }
   return(t(map))
}
a <- assignment(10,7,3)


Dan

Daniel Nordlund
Bothell, WA USA