notes

   1 Assignment problems arise in a variety of settings.
   2 For funding agencies such as NSF program directors
   3 that co-ordinate panels, assigning proposals to
   4 reviewers is a major challenge. It is important that each proposal be
   5 reviewed by qualified experts, and at the same time we would like the
   6 workload across different reviewers to be roughly balanced. The same
   7 issue arises for a program committee chair, who may have to assign
   8 literally hundreds of papers to a program committee consisting of
   9 thirty to forty program committee members.
  10
  11 {\em What does CMT use? What does Easychair use?}
  12
  13 From now on we will focus on the problem of assigning papers to
  14 reviewers.
  15 We assume that each reviewer is given access to the
  16 list of papers to be reviewed, and provides input on their
  17 preferences by giving a ``desirability'' score to each paper.
  18 We also assume that each paper  has to be reviewed by $r$
  19 reviewers.
  20
  21 We do not consider stable marriage type preference lists,
  22 because a strict ranking of papers would be rather tedious
  23 to produce. In this scheme, the papers are essentially grouped
  24 into a few categories.
  25
  26
  27 Ideally, from the perspective of the papers, we would like to
  28 assign each paper the $r$ ``best'' reviewers for the paper.
  29 Ofcourse, this would lead to a load imbalanced solution where
  30 the load on some program committee members is very high, and the
  31 load on others is low. On the other hand, we could insist
  32 on a perfectly load balanced solution in which the number
  33 of papers assigned to each program committee member do not
  34 exceed $\lceil rN/P  \rceil$, where $N$ is the number of
  35 submissions and $P$ is the number of program committee members.
  36 Recall that each paper needs $r$ reviewers, so a total of $rN$
  37 reviews need to be generated. However this may lead to a solution
  38 which is not optimal from the perspective of the papers.
  39
  40 One of our goals is to study precisely this tradeoff, and allow each
  41 reviewer to have upto $\lceil rN/P  \rceil + C$ papers assigned to
  42 them, where $C$ is the {\em imbalance factor}. The main question
  43 we consider is: is it possible to obtain a high quality
  44 assignment with a fairly low value of $C$?
  45
  46 One can ask the same question from the perspective of the reviewers
  47 as well. Each reviewer would ideally like papers
  48 that are the ``most desirable'' from their point of view.
  49
  50 {\em Stinkers} are papers that pretty much no-one wanted to review.
  51 We would like to spread the load of the stinkers as evenly as possible.
  52
  53 \section{Formulation as a Min Cost Flow Problem}
  54
  55 \section{Experimental Results}
  56
  57 \section{Conclusions}
  58