file.
Also: modernize the method of excluding .git from Eclipse.
--- /dev/null
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<launchConfiguration type="org.eclipse.ui.externaltools.ProgramBuilderLaunchConfigurationType">
+<stringAttribute key="org.eclipse.debug.core.ATTR_REFRESH_SCOPE" value="${working_set:<?xml version="1.0" encoding="UTF-8"?> <launchConfigurationWorkingSet factoryID="org.eclipse.ui.internal.WorkingSetFactory" label="match paper outputs" name="match paper outputs"> <item factoryID="org.eclipse.ui.internal.model.ResourceFactory" path="/match/paper" type="2"/> </launchConfigurationWorkingSet>}"/>
+<booleanAttribute key="org.eclipse.debug.ui.ATTR_LAUNCH_IN_BACKGROUND" value="false"/>
+<stringAttribute key="org.eclipse.ui.externaltools.ATTR_BUILD_SCOPE" value="${working_set:<?xml version="1.0" encoding="UTF-8"?> <launchConfigurationWorkingSet factoryID="org.eclipse.ui.internal.WorkingSetFactory" label="match paper inputs" name="match paper inputs"> <item factoryID="org.eclipse.ui.internal.model.ResourceFactory" path="/match/paper" type="2"/> </launchConfigurationWorkingSet>}"/>
+<stringAttribute key="org.eclipse.ui.externaltools.ATTR_LOCATION" value="/usr/bin/make"/>
+<stringAttribute key="org.eclipse.ui.externaltools.ATTR_RUN_BUILD_KINDS" value="full,incremental,auto,"/>
+<booleanAttribute key="org.eclipse.ui.externaltools.ATTR_TRIGGERS_CONFIGURED" value="true"/>
+<stringAttribute key="org.eclipse.ui.externaltools.ATTR_WORKING_DIRECTORY" value="${workspace_loc:/match/paper}"/>
+</launchConfiguration>
</dictionary>
</arguments>
</buildCommand>
+ <buildCommand>
+ <name>org.eclipse.ui.externaltools.ExternalToolBuilder</name>
+ <triggers>auto,full,incremental,</triggers>
+ <arguments>
+ <dictionary>
+ <key>LaunchConfigHandle</key>
+ <value><project>/.externalToolBuilders/make match paper.launch</value>
+ </dictionary>
+ </arguments>
+ </buildCommand>
</buildSpec>
<natures>
</natures>
- <linkedResources>
- <link>
- <name>.git</name>
- <type>2</type>
- <location>/home/matt/Emptydir</location>
- </link>
- </linkedResources>
+ <filteredResources>
+ <filter>
+ <id>0</id>
+ <name></name>
+ <type>10</type>
+ <matcher>
+ <id>org.eclipse.ui.ide.multiFilter</id>
+ <arguments>1.0-name-matches-true-false-.git</arguments>
+ </matcher>
+ </filter>
+ </filteredResources>
</projectDescription>
+++ /dev/null
-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}
-
--- /dev/null
+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.*
--- /dev/null
+#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
--- /dev/null
+\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}
--- /dev/null
+#!/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."