CS 660 Assignment 7
Due at the beginning of class on Thursday, April 29th
This assignment asks you to experiment with paper assignments.
The data will be available---I will email you the link or links for data
from actual conferences (anonymized, of course).
What to do
Choose at least two optimality criteria from the following, and
compute optimal assignments with respect to your criteria.
Re-evaluate your assignments according to each of the criteria.
Criteria
- Maximum total utility
- Maximum number of highest-rated matches
- Minimum number of lowest-rated matches
- Maximin
- Leximax
How to do it
Any of the utilitarian criteria can be modeled as network flow problems, which
can, in turn, be modeled as linear
programs (Linear Programming: Chapter 13. Network Flows: Algorithms. Robert
J. Vanderbei). Wikipedia gives many
other network flow algorithms.
Once you have set up an evaluation method for your criterion, you could use a
local search algorithm. For instance, you can start with a random assignment,
and look at neighboring assignments in which you have swapped one paper of
papers. Remember that local search algorithms are not guaranteed to find optimal
solutions, but for small problems, many random restarts increase the odds of
finding optimal examples.
To hand in
- The usual description (what criteria you used, how you computed the optimal
or possibly-optimal assignments).
- The output of your computation.
- Statistics on the computation.
- Your observations on the ease of computation, and the relative
optimality of the assignments.