From f3084293a1cf94d98fb44a7d427f012361c28afc Mon Sep 17 00:00:00 2001 From: Matt McCutchen Date: Sat, 11 Feb 2012 17:53:39 -0800 Subject: [PATCH] Add a slightly cleaned-up version of the paper, superseding the "notes" file. Also: modernize the method of excluding .git from Eclipse. --- .externalToolBuilders/make match paper.launch | 10 + .project | 28 ++- notes | 58 ----- paper/Makefile | 40 +++ paper/flow.fig | 165 +++++++++++++ paper/paper.tex | 229 ++++++++++++++++++ paper/retex | 82 +++++++ 7 files changed, 547 insertions(+), 65 deletions(-) create mode 100644 .externalToolBuilders/make match paper.launch delete mode 100644 notes create mode 100644 paper/Makefile create mode 100644 paper/flow.fig create mode 100644 paper/paper.tex create mode 100755 paper/retex diff --git a/.externalToolBuilders/make match paper.launch b/.externalToolBuilders/make match paper.launch new file mode 100644 index 0000000..252fa50 --- /dev/null +++ b/.externalToolBuilders/make match paper.launch @@ -0,0 +1,10 @@ + + + + + + + + + + diff --git a/.project b/.project index 165f368..00459f2 100644 --- a/.project +++ b/.project @@ -15,14 +15,28 @@ + + org.eclipse.ui.externaltools.ExternalToolBuilder + auto,full,incremental, + + + LaunchConfigHandle + <project>/.externalToolBuilders/make match paper.launch + + + - - - .git - 2 - /home/matt/Emptydir - - + + + 0 + + 10 + + org.eclipse.ui.ide.multiFilter + 1.0-name-matches-true-false-.git + + + diff --git a/notes b/notes deleted file mode 100644 index aca2880..0000000 --- a/notes +++ /dev/null @@ -1,58 +0,0 @@ -Assignment problems arise in a variety of settings. -For funding agencies such as NSF program directors -that co-ordinate panels, assigning proposals to -reviewers is a major challenge. It is important that each proposal be -reviewed by qualified experts, and at the same time we would like the -workload across different reviewers to be roughly balanced. The same -issue arises for a program committee chair, who may have to assign -literally hundreds of papers to a program committee consisting of -thirty to forty program committee members. - -{\em What does CMT use? What does Easychair use?} - -From now on we will focus on the problem of assigning papers to -reviewers. -We assume that each reviewer is given access to the -list of papers to be reviewed, and provides input on their -preferences by giving a ``desirability'' score to each paper. -We also assume that each paper has to be reviewed by $r$ -reviewers. - -We do not consider stable marriage type preference lists, -because a strict ranking of papers would be rather tedious -to produce. In this scheme, the papers are essentially grouped -into a few categories. - - -Ideally, from the perspective of the papers, we would like to -assign each paper the $r$ ``best'' reviewers for the paper. -Ofcourse, this would lead to a load imbalanced solution where -the load on some program committee members is very high, and the -load on others is low. On the other hand, we could insist -on a perfectly load balanced solution in which the number -of papers assigned to each program committee member do not -exceed $\lceil rN/P \rceil$, where $N$ is the number of -submissions and $P$ is the number of program committee members. -Recall that each paper needs $r$ reviewers, so a total of $rN$ -reviews need to be generated. However this may lead to a solution -which is not optimal from the perspective of the papers. - -One of our goals is to study precisely this tradeoff, and allow each -reviewer to have upto $\lceil rN/P \rceil + C$ papers assigned to -them, where $C$ is the {\em imbalance factor}. The main question -we consider is: is it possible to obtain a high quality -assignment with a fairly low value of $C$? - -One can ask the same question from the perspective of the reviewers -as well. Each reviewer would ideally like papers -that are the ``most desirable'' from their point of view. - -{\em Stinkers} are papers that pretty much no-one wanted to review. -We would like to spread the load of the stinkers as evenly as possible. - -\section{Formulation as a Min Cost Flow Problem} - -\section{Experimental Results} - -\section{Conclusions} - diff --git a/paper/Makefile b/paper/Makefile new file mode 100644 index 0000000..11b16fd --- /dev/null +++ b/paper/Makefile @@ -0,0 +1,40 @@ +figures = flow +inputs = + +all: paper.pdf #paper.ps + +.DELETE_ON_ERROR: + +paper.pdf: $(inputs) $(addsuffix .pdf_t,$(figures)) $(addsuffix .pdf,$(figures)) +# Note: paper.dvi refers to the PostScript figures by filename instead of +# embedding them. The figures are read once when the references are placed in +# paper.dvi and again when the figures are embedded in streaming.ps, so we +# list them as prerequisites of both files. +paper.dvi: $(inputs) $(addsuffix .pstex_t,$(figures)) $(addsuffix .pstex,$(figures)) +paper.ps: $(addsuffix .pstex,$(figures)) + +# TeX compiling rules +%.pdf: %.tex +# Avoid writing the file in place because that seems to make evince crash. + rm -f $@ + ./retex pdflatex $* +%.dvi: %.tex + retex latex $* +%.ps: %.dvi + dvips $< -o $@ + +# Figure exporting rules (equivalent to Xfig's export command) +%.pdf: %.fig +# Force portrait mode to prevent rotation. + fig2dev -L pdftex -p dummy $< $@ +%.pdf_t: %.fig + fig2dev -L pdftex_t -p $*.pdf $< $@ +%.pstex: %.fig + fig2dev -L pstex -p dummy $< $@ +%.pstex_t: %.fig + fig2dev -L pstex_t -p $*.pstex $< $@ + +generated_files = $(addprefix paper,.aux .bbl .blg .dvi .log .pdf .ps .toc) \ + $(foreach fn,$(figures),$(fn).pdf $(fn).pdf_t $(fn).pstex $(fn).pstex_t) +clean: + rm -f $(generated_files) *.retex-keep.* diff --git a/paper/flow.fig b/paper/flow.fig new file mode 100644 index 0000000..3b3696e --- /dev/null +++ b/paper/flow.fig @@ -0,0 +1,165 @@ +#FIG 3.2 Produced by xfig version 3.2.5 +Landscape +Center +Inches +Letter +100.00 +Single +-2 +1200 2 +5 1 0 1 0 7 50 -1 -1 0.000 0 1 1 0 6387.500 2250.000 5700 1650 5475 2250 5700 2850 + 0 0 1.00 60.00 120.00 +5 1 0 1 0 7 50 -1 -1 0.000 0 1 1 0 6387.500 4575.000 5700 3975 5475 4575 5700 5175 + 0 0 1.00 60.00 120.00 +5 1 0 3 0 7 50 -1 -1 0.000 0 1 1 0 -68.534 1103.017 600 3975 1500 3600 2250 2925 + 1 1 3.00 45.00 90.00 +5 1 0 3 0 7 50 -1 -1 0.000 0 1 1 0 2653.125 2671.875 525 4050 1275 4800 2250 5175 + 1 1 3.00 45.00 90.00 +5 1 0 3 0 7 50 -1 -1 0.000 0 0 1 0 7180.556 5386.111 525 3900 1125 2250 2250 675 + 1 1 3.00 45.00 90.00 +6 1950 375 2700 2100 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2325 600 75 75 2325 600 2325 675 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2325 1275 75 75 2325 1275 2325 1350 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2325 1875 75 75 2325 1875 2325 1950 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 1950 375 2700 375 2700 2100 1950 2100 1950 375 +2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 3.00 45.00 90.00 + 2325 675 2325 1200 +2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 3.00 45.00 90.00 + 2325 1350 2325 1800 +-6 +6 5625 2400 5925 2850 +5 1 0 1 0 7 50 -1 -1 0.000 0 1 1 0 6075.000 2625.000 5775 2400 5700 2625 5775 2850 + 0 0 1.00 60.00 120.00 +5 1 0 1 0 7 50 -1 -1 0.000 0 0 1 0 5475.000 2625.000 5775 2400 5850 2625 5775 2850 + 0 0 1.00 60.00 120.00 +-6 +6 5625 4725 5925 5175 +5 1 0 1 0 7 50 -1 -1 0.000 0 1 1 0 6075.000 4950.000 5775 4725 5700 4950 5775 5175 + 0 0 1.00 60.00 120.00 +5 1 0 1 0 7 50 -1 -1 0.000 0 0 1 0 5475.000 4950.000 5775 4725 5850 4950 5775 5175 + 0 0 1.00 60.00 120.00 +-6 +6 1950 2700 2700 4425 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2325 2925 75 75 2325 2925 2325 3000 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2325 3600 75 75 2325 3600 2325 3675 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2325 4200 75 75 2325 4200 2325 4275 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 1950 2700 2700 2700 2700 4425 1950 4425 1950 2700 +2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 3.00 45.00 90.00 + 2325 3000 2325 3525 +2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 3.00 45.00 90.00 + 2325 3675 2325 4125 +-6 +6 1950 4950 2700 6675 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2325 5175 75 75 2325 5175 2325 5250 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2325 5850 75 75 2325 5850 2325 5925 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 2325 6450 75 75 2325 6450 2325 6525 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 1950 4950 2700 4950 2700 6675 1950 6675 1950 4950 +2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 3.00 45.00 90.00 + 2325 5250 2325 5775 +2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 3.00 45.00 90.00 + 2325 5925 2325 6375 +-6 +6 5925 300 8925 1425 +4 0 0 50 -1 0 12 0.0000 4 180 2625 5925 450 Reviewer 1 is an expert reviewer\001 +4 0 0 50 -1 0 12 0.0000 4 180 2715 5925 675 for paper 1, but reviewer 2 is only\001 +4 0 0 50 -1 0 12 0.0000 4 180 2985 5925 900 a knowledgable reviewer for paper 1.\001 +4 0 0 50 -1 0 12 0.0000 4 135 2880 5925 1125 Reviewer 3 does not want to review\001 +4 0 0 50 -1 0 12 0.0000 4 180 645 5925 1350 paper 1.\001 +-6 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 525 3975 75 75 525 3975 525 4050 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 8422 3922 75 75 8422 3922 8422 3997 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5775 1650 75 75 5775 1650 5775 1725 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5775 2325 75 75 5775 2325 5775 2400 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5775 2925 75 75 5775 2925 5775 3000 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5775 3975 75 75 5775 3975 5775 4050 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5775 4650 75 75 5775 4650 5775 4725 +1 3 0 1 0 7 50 -1 -1 0.000 1 0.0000 5775 5250 75 75 5775 5250 5775 5325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 600 3975 2250 2925 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 525 4050 2250 5175 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 5850 3000 8325 3900 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 5850 5250 8325 3975 +2 2 2 1 0 7 50 -1 -1 3.000 0 0 -1 0 0 5 + 5400 1425 6150 1425 6150 3150 5400 3150 5400 1425 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 5775 1725 5775 2250 +2 2 2 1 0 7 50 -1 -1 3.000 0 0 -1 0 0 5 + 5400 3750 6150 3750 6150 5475 5400 5475 5400 3750 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 5775 4050 5775 4575 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 2400 600 5700 1650 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 2400 2925 5700 2325 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 5025 6525 6300 6525 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 525 3900 2250 675 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 0 0 1.00 60.00 120.00 + 2400 6450 5700 3000 +2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 1 0 2 + 1 1 3.00 45.00 90.00 + 5025 6150 6225 6150 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 2775 1575 2400 900 +2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2 + 2775 1575 2400 1650 +4 0 0 50 -1 0 12 0.0000 4 135 1740 1950 2400 Nodes for Reviewer 1\001 +4 0 0 50 -1 0 12 0.0000 4 135 1740 1800 4725 Nodes for Reviewer 2\001 +4 0 0 50 -1 0 12 0.0000 4 135 1740 1725 6900 Nodes for Reviewer 3\001 +4 0 0 50 -1 0 12 0.0000 4 180 1425 4950 5775 Nodes for paper 2\001 +4 0 0 50 -1 0 12 0.0000 4 180 1185 5175 6825 (capacity,cost)\001 +4 0 0 50 -1 0 12 0.0000 4 180 1425 4950 3450 Nodes for paper 1\001 +4 0 0 50 -1 0 12 0.0000 6 195 720 6300 4050 $p^1_2$\001 +4 0 0 50 -1 0 12 0.0000 6 195 720 6375 5400 $p^3_2$\001 +4 0 0 50 -1 0 12 0.0000 6 195 720 6300 4725 $p^2_2$\001 +4 0 0 50 -1 0 12 0.0000 4 165 330 7200 3375 (r,0)\001 +4 0 0 50 -1 0 12 0.0000 4 165 330 7200 4350 (r,0)\001 +4 0 0 50 -1 0 12 0.0000 6 180 675 2850 600 $r^1_1$\001 +4 0 0 50 -1 0 12 0.0000 6 180 675 2850 1950 $r^3_1$\001 +4 0 0 50 -1 0 12 0.0000 6 180 675 2850 1275 $r^2_1$\001 +4 0 0 50 -1 0 12 0.0000 6 180 675 2850 3000 $r^1_2$\001 +4 0 0 50 -1 0 12 0.0000 6 180 675 2850 5250 $r^1_3$\001 +4 0 0 50 -1 0 12 0.0000 6 180 675 2850 3675 $r^2_2$\001 +4 0 0 50 -1 0 12 0.0000 6 180 675 2850 5925 $r^2_3$\001 +4 0 0 50 -1 0 12 0.0000 6 180 675 2850 4275 $r^3_2$\001 +4 0 0 50 -1 0 12 0.0000 6 180 675 2850 6525 $r^3_3$\001 +4 0 0 50 -1 0 12 0.0000 4 165 390 975 3450 (L,0)\001 +4 0 0 50 -1 0 12 0.0000 4 165 390 975 4275 (L,0)\001 +4 0 0 50 -1 0 12 0.0000 6 195 1710 3825 900 $(1,(10+p_{11})^2)$\001 +4 0 0 50 -1 0 12 0.0000 6 195 1710 3825 2850 $(1,(10+p_{21})^2)$\001 +4 0 0 50 -1 0 12 0.0000 4 180 1125 5100 6375 Parallel edges\001 +4 0 0 50 -1 0 12 0.0000 6 180 840 4800 2025 $(1,-c_1)$\001 +4 0 0 50 -1 0 12 0.0000 6 195 930 5850 2025 $(\\infty,0)$\001 +4 0 0 50 -1 0 12 0.0000 6 195 2205 5925 2700 $(1,-c_2)$ and $(\\infty, 0)$\001 +4 0 0 50 -1 0 12 0.0000 6 195 720 6225 3000 $p^3_1$\001 +4 0 0 50 -1 0 12 0.0000 6 195 720 6225 2400 $p^2_1$\001 +4 0 0 50 -1 0 12 0.0000 6 195 720 6225 1725 $p^1_1$\001 +4 0 0 50 -1 0 12 0.0000 4 135 135 1050 4950 C\001 +4 0 0 50 -1 0 12 0.0000 4 135 135 900 2175 C\001 +4 0 0 50 -1 0 12 0.0000 4 135 135 1425 3825 C\001 +4 0 0 50 -1 0 12 0.0000 4 165 390 1350 2550 (L,0)\001 +4 0 0 50 -1 0 12 0.0000 4 135 360 2850 1650 L+C\001 diff --git a/paper/paper.tex b/paper/paper.tex new file mode 100644 index 0000000..2882ac9 --- /dev/null +++ b/paper/paper.tex @@ -0,0 +1,229 @@ +\documentclass[11pt]{article} +\usepackage{url} +\usepackage[square,comma,numbers]{natbib} +\usepackage{color} + +% Figure stuff. To add a new figure named `foo.fig', put +% `\includexfig{foo}' in the appropriate place and add `foo' to the +% figures line at the top of the Makefile. +\usepackage{ifpdf} +\ifpdf + \usepackage[pdftex]{graphicx} + \def\includexfig#1{\input{#1.pdf_t}} +\else + \usepackage[dvips]{graphicx} + \def\includexfig#1{\input{#1.ps_t}} +\fi + +\usepackage{amssymb, amsmath, amsthm} +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}{Lemma} + +\usepackage[letterpaper,left=2.6cm,right=2.6cm,top=2.6cm,bottom=2.6cm]{geometry} + +\usepackage{floatflt} +\usepackage{pstricks} +\usepackage{delarray} + +\title{Assigning Reviewers to Proposals} + +\author{ +Samir Khuller\thanks{Research currently supported by CCF-0728839. +Email:{\tt samir@cs.umd.edu}.}\\ +Dept.\ of Computer Science\\ +University of Maryland, College Park MD 20742. +\and +Richard Matthew McCutchen\thanks{ +The bulk of this work was done while Matt was at the Dept.\ of Computer Science, +University of Maryland, College Park, and supported by REU Supplement to +CCF-0430650. Current email: {\tt matt@mattmccutchen.net}.}\\ +%Department of Computer Science\\ +%University of Maryland, College Park, MD 20742. +} + +\date{} + +\begin{document} + +\maketitle + +%\begin{abstract} +% +%\end{abstract} + +\section{Introduction} +Assignment problems arise in a variety of settings. +For funding agencies such as NSF program directors +that co-ordinate panels, assigning proposals to +reviewers is a major challenge. It is important that each proposal receive +sufficient review by qualified experts, and at the same time we would like to +roughly balance the workload across reviewers and to honor the reviewers' +preferences for which proposals they would like to read. The same +issue arises for a program committee chair, who may have to assign +literally hundreds of papers to a program committee consisting of +thirty to forty program committee members. + +%{\em What does CMT use? What does Easychair use?} + +From now on we will focus on the problem of assigning papers to +reviewers. +We assume that each reviewer is given access to the +list of papers to be reviewed, and gives each paper both a ``desirability'' +score indicating his/her level of interest in reviewing the paper and an +``expertise'' score indicating how qualified he/she is to evaluate the paper. +(Some organizations may choose to use a single set of scores for both +desirability and expertise. We believe that making this distinction may better +model the real-world objective.) +A reviewer may also report a conflict of interest with a particular paper, +meaning that he/she is forbidden to review the paper. + +We do not consider stable marriage type preference lists, +because a strict ranking of papers would be rather tedious +to produce. In this scheme, the papers are essentially grouped +into a few categories. + +Let $N$ be the number of papers and $P$ be the number of reviewers. +Suppose that each paper needs $r$ reviews, so a total of $rN$ +reviews need to be generated. +Ideally, from the perspective of the papers, we would like to +assign each paper the $r$ most qualified reviewers for the paper. +Of course, this could lead to a load imbalanced solution where +the load on some program committee members is very high, and the +load on others is low. On the other hand, we could insist +on a perfectly load balanced solution in which the number +of papers assigned to each program committee member does not +exceed $L= \lceil rN/P \rceil$. However, this may lead to a solution +which is not optimal from the perspective of the papers. + +One of our goals is to study precisely this tradeoff, and allow each +reviewer to be assigned up to $L + C$ papers, +where $C$ is the {\em load tolerance}. We consider the question: +is it possible to obtain a high quality +assignment with a fairly low value of $C$? One can also ask whether, +in such an assignment, the reviewers receive the papers that they would +have most liked to review. + +{\em Stinkers} are papers that pretty much no-one wanted to review. +We would like to spread the load of the stinkers as evenly as possible. + + +\section{Formulation as a Min-Cost Flow Problem} + +Our main approach is to formulate this as a min-cost flow problem. +The construction is somewhat involved in order to incorporate all +the appropriate incentives. It makes +use of sets of ``parallel edges'' of different costs connecting a +single pair of nodes $(x, y)$ to allow flow to be sent from $x$ to $y$ +at a cost that grows faster than linear in the amount of the flow. For +example, if there are five unit-capacity edges from $x$ to $y$ of costs +1, 3, 5, 7, and 9, then any integer amount $f \le 5$ of flow can be +sent from $x$ to $y$ at a cost of $f^2$. + +The construction is done as follows: we have a source $s$ and a sink $t$. +For each paper $j$ we create a set of nodes $p^1_j, p^2_j,p^3_j$, and for each +reviewer $i$ we create a set of nodes $r^1_i, r^2_i, r^3_i$. (The rationale +for these sets is discussed below.) See Figure~\ref{flow-fig} for an +example. Flow can pass from $s$ through one or more of the nodes $r^t_i$ and +one or more of the nodes $p^t_j$ to the sink to represent a review +by reviewer $i$ of paper $j$. + +Each paper has an edge of capacity $r$ to +the sink, indicating that it needs $r$ reviews. In general, these +edges will constitute the min cut, so any max flow will saturate them +and thereby provide all the required reviews. We take the min-cost +max flow in order to provide the reviews in the ``best'' possible way. + +Each reviewer has a zero-cost edge of capacity $L$ from the source so that +he/she can be assigned $L$ papers. If that were all, we would get a perfectly +load-balanced solution, but we may be able to improve the quality of the +assignments by allowing some imbalance. +Therefore, we allow each reviewer to be overloaded by up to $C$ papers +($C$ is the load imbalance parameter) via a set +of $C$ additional unit-capacity edges from the source. We make the cost of the +$l$th edge an increasing function $f(l)$ to provide an incentive to +balance load across reviewers. Since $2f(1) < f(1) + f(2)$, +a solution that loads two reviewers each by $L+1$ will be preferred +to a solution that loads one reviewer by $L$ and the other by $L+2$ +unless the load imbalance in the second solution is outweighed by +other benefits. + +For each reviewer $i$ and proposal $j$, there is a unit-capacity edge from $i$ +to $j$ allowing that assignment to be made, unless the reviewer declared a +conflict of interest, in which case the edge is not present. The edge has +cost $(10 + p_{ij})^2$, where $p_{ij}$ is the preference value +expressed by reviewer $i$ for proposal $j$. +We assume $p_{ij}$ is a value between 1 and 40 (as used by NSF). +The cost function was chosen to provide an incentive to avoid really bad +assignments without completely masking the difference between a good assignment +and an excellent assignment. + +These purely additive assignment costs make the algorithm prefer better +assignments in general but do nothing to promote fairness among reviewers or +among papers. To do that, we introduce additional reviewer-side costs and +paper-side bonuses. With respect to a +reviewer $i$, we classify papers as interesting (preference value 1 to 15), boring +(16 to 25), or very boring (26 to 40). The edge for reviewer $i$ and paper +$j$ leaves from $r^1_i$ if $j$ is interesting, $r^2_i$ if $j$ is boring, or +$r^3_i$ if $j$ is very boring. Since all edges from the source enter $r^1_i$, +flow for boring and very boring assignments is forced to pass through a set of +parallel edges from $r^1_i$ to $r^2_i$, and flow for very boring assignments +must pass through an additional set of parallel edges from $r^2_i$ to $r^3_i$. +In each of these sets, we make the cost of the $l$th edge an increasing +function of $l$ to provide an incentive to balance the load of boring +assignments in the same way as for overload. + +Similarly, we wish to guarantee each paper at least one or two good reviews. +With respect to a paper $j$, we classify reviewers as expert (preference value +1 to 10), knowledgeable (11 to 20), or general (21 to 40). Edges representing +expert reviews enter $p^1_j$, edges for knowledgeable reviews enter $p^2_j$, +and edges for general reviews enter $p^3_j$; the edge to the sink leaves +$p^3_j$. A paper's first knowledgeable (or expert) review scores a bonus $c_2$ +by traversing a unit-capacity edge of cost $-c_2$ from $p^2_j$ to $p^3_j$, +and an additional expert review scores another bonus $c_1$ by traversing a +unit-capacity edge of cost $-c_1$ from $p^1_j$ to $p^3_j$. +In addition to the bonus edges, +there are edges of zero cost and unlimited capacity that reviews can follow +from $p^1_j$ to $p^2_j$ and from $p^2_j$ to $p^3_j$ in order to reach the sink. +The choice to offer bonuses for two reviews was based on the value $r = 3$; +this would be easy to change for other values of $r$. + +The cost of a flow is the sum of its reviewer overload costs, +assignment costs, and reviewer boring / very boring load costs, +minus paper bonuses. Any one of those components can be traded off against +the others. We attempted to assign reasonable weights to each component, +but it is difficult to know without testing the algorithm on real data. +In any event, all the parameters are easy to tune to realize the priorities +of a particular application. + +\begin{figure*} +\begin{center} +\centerline{\includexfig{flow}} +\caption{Flow Construction.} +\label{flow-fig} +\end{center} +\end{figure*} + + +\section{Experimental Results} +Waiting for data from NSF. + +Synthetic Data. + +\section{Conclusions} + +The source code for the current version of the proposal matcher may be +browsed or downloaded at: +\[\hbox{\url{TODO}}\] + +\begin{thebibliography}{99} + +\bibitem{Flow} +R. Ahuja, T. Magnanti and J. Orlin. +Network Flows: Theory and Applications. +{\em Prentice Hall}. + + + +\end{thebibliography} + +\end{document} diff --git a/paper/retex b/paper/retex new file mode 100755 index 0000000..447aa71 --- /dev/null +++ b/paper/retex @@ -0,0 +1,82 @@ +#!/bin/bash +# usage: retex [--bibtex] CMD INPUTNAME (without .tex) + +set -e + +# Add a bibtex option for the streaming notes. +# Since the bibtex needs to be part of the fixed-pointing, I unfortunately don't +# see a better way to handle it than as part of retex. - Matt 2008-09-02 +if [ "$1" == --bibtex ]; then + bibtex=1 + shift +fi + +if [ $# != 2 ]; then + echo >&2 'usage: retex [--bibtex] CMD INPUTNAME (without .tex)' + exit 1 +fi + +cmd="$1" +in="$2" +shift 2 + +# Just Work if passed `foo.tex'. +if [ "$in" != "${in%.tex}" ]; then + in="${in%.tex}" +fi + +function run { + if [ $bibtex ] && [ -r "$in.aux" ]; then + echo "[$iter] Running bibtex..." + bibtex "$in.aux" + # Work around \href commands getting line-broken in places that + # break things ~ Matt 2010-12-17 + sed -i -e '/%$/{N; s/%\n//}; /\\href$/{N; s/\n/ /}' "$in.bbl" + fi + echo "[$iter] Running $2..." + "$cmd" -file-line-error -halt-on-error "$in" +} + +function compare { + echo "Comparing files..." + for f in "$in."*; do + # ignore pdfs because they have a nonreproducible "ID" at the end + # and logs because they have a less-reproducible time; neither are read + if [ "$f" == "${f#$in.retex-keep.}" ] && [ "$f" == "${f%.pdf}" ] && [ "$f" == "${f%.log}" ]; then + suf="${f#$in.}" + cmp "$in.retex-keep.$suf" "$in.$suf" || return $? + fi + done + echo "Reached a fixed point." +} + +function keep { + echo "Keeping files..." + for f in "$in."*; do + if [ "$f" == "${f#$in.retex-keep.}" ]; then + suf="${f#$in.}" + cp "$in.$suf" "$in.retex-keep.$suf" + fi + done +} + +function clean { + echo "Cleaning up kept files..." + rm -f "$in.retex-keep."* +} + +iter=0 +keep +run || exit $? +limit=10 +while ! compare; do + iter=$(($iter + 1)) + if [ $iter -ge $limit ]; then + echo "Did not reach a fixed point in $limit tries." + exit 2 + fi + keep + run || exit $? +done +clean +echo "Successful." -- 2.34.1