A combinatorial assignment problem

I have this combinatorial assignment problem: K candidates apply for a job. There are R referees available to review their resumes and make a recommendation. Suppose that we would like M referees to review each candidate (M < R). How would you 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).

Of course, there are some constraints that make the assignment a bit challenging. We would like to have an even distribution of the number of candidates reviewed by each referee. We would also like to have some randomness or "mixing" in the assignment such that it is probable for any candidate to be assigned to any M-plet of referees. Is this an instance of a well known problem in combinatorics? Any hints or references to algorithms is appreciated.

You can get as even a distribution as possible if you assign the first candidate to the first $M$ referees, the second candidate to the next $M$, the third to the next $M$ and so on, wrapping around to the start when needed. So candidate $k$ is given to reviewers $((k-1)M+1)$ through $kM \pmod R$ It gets harder if you want the candidates "sprinkled" through the referees. With my scheme, if $M$ is a factor of $R$, a set of referees will all see the same candidates and you won't get any standardization between referees. Maybe that doesn't matter.

• Thanks, Ross. I would like to avoid the situation you mentioned when R is a multiple of M. I have edited the question. – user67724 Apr 30 '14 at 20:42
• It is hard to give a general rule, but each time you go through the $R$ reviewers you can take them in a different order. If there is a number coprime to $R$ and close to $\sqrt R$ you can use that as an increment for the second round. So if $R=13$, the first time through you take them in the order $1,2,3,4,\dots 13$, then the second you take them $5,9,13,\dots 1$ and so on. – Ross Millikan Apr 30 '14 at 20:55

If you think of reviewers as servers and candidates as tasks, then this becomes a load-balancing problem. The literature on this topic is quite extensive.

One of the algorithms with nice properties is:

• For each load (i.e. the number of tasks the server is assigned) have a random permutation (you can generate them on-demand).
• Assign the task to an available server with the lowest load.
• Break the ties according to the permutation corresponding to that load.

I hope this helps $\ddot\smile$

• Thanks for the pointer to load-balancing problem. Does it matter that there is additional requirement that each task must be done by M servers? – user67724 Apr 30 '14 at 21:30
• Also it seems to me that load-balancing is a dynamic scheduling problem, that is you assign a new task to a server in real time, whereas I am interested in a static situation where all the tasks are already there to be assigned. – user67724 Apr 30 '14 at 21:34
• Yes, load balancing is a dynamic problem, but that does not mean you cannot use it in your case. As for the additional requirement: add M copies of each task. – dtldarek Apr 30 '14 at 21:42
• Can you suggest a specific article or book or website? Thanks. – user67724 Apr 30 '14 at 21:43
• @user67724 I would start with On-line Load Balancing by Y. Azar, perhaps Algorithmics of Two-Sided Matching Problems by D. J. Abraham could be of interest too. Just search for some survey. – dtldarek Apr 30 '14 at 21:53