0
$\begingroup$

A professor will assign research papers to his students as a partial fulfilment of the requirements of a graduate course. There are six students enrolled in the course and each student will be assigned exactly two research papers. The professor has selected twelve research papers and also determined the expected workload (in hours) required to read,understand and present each of these papers.

An important concern of the professor in organizing the assignments is to be fair to all students by keeping the variance of student workloads as small as possible. Let $v_n$ be the workload associated with the $n$'th research paper,and suppose that a student's workload is the sum of the workloads associated with the research papers he/she is responsible for.

For instance, the total workload of a student responsible for the 1'st and 5'th paper is equal to $v_1+v_5$. Formulate an IP to determine how to assign papers to students to minimize the variance of students workloads. Note that, for a given set of values $\{x_1,x_2,..,x_n\}$ the variance is a non-linear expression defined as

$\operatorname{Variance}=\sum_{i=1}^n (x_i - \overline x)$

where $\overline x$ is the arithmetic mean.

1 Answers 1

1

Note that $\overline x=2\overline v$ does not dpend on the assignment chosen. Therefore we can simply minimize $\sum x_i^2$, which is just $\sum v_i^2$ plus the sum of all products $2v_iv_j$ where papers $i,j$ are assigned to the same student. Note that the difference between $v_1v_2+v_3v_4$ and $v_1v_4+v_3v_2$ is $(v_1-v_3)(v_4-v_2)$, hence in an optimal assignment $(v_1-v_3)(v_4-v_2)\ge 0$ whenever $(v_1,v_2)$, $(v_3,v_4)$ are assignments to two students. If wlog. $v_1\le v_2$ and $v_3\le v_4$, this implies $v_1< v_3\le v_4< v_2$ or $v_1=v_3$ or $v_2=v_4$. This suggests that the $i$th student should get the $i$th hardest and the $i$th simplest assignment (at least if all $v_i$ are distinct, but this strategy is also optimal in case ofsome equal $v_i$'s as can be seen by modifying these $v_i$ by some small $\epsilon$)