A Reviewer Assignment Problem
Consider there are some reviewers and some papers. Each reviewer can review exactly one paper, and each reviewer is qualified to review some subset of papers. We are interested in maximizing the number of papers reviewed by at least reviewer, then under that constraint, maximize the paper reviewed by reviewer, etc. This make sure we are being fair in evaluating papers. It would try to avoid the case where most paper getting small number of reviews and a few papers getting unreasonable number of reviews.
Formally, we are given a bipartite graph of vertices and edges. A subset of edges is called a semi-matching, if for all . For a subset of edges , let to be the number of vertices in with degree at least . We want to find a semi-matching , such that is lexicographically maximum.
When , if minimizes the sum of the function for any strictly convex increasing function , then is lexicographically maximum. The problem therefore can be reduced to min-cost flow can be applied here directly, and obtain a polynomial time algorithm .
When , the problem is NP-hard, since it would imply we have to maximized , and this is already NP-hard because exact cover by -sets. That is, given a collection of sets of size each. Decide if there exists a subcollection that forms a partition of the universe.
The only unresolved case is . Interestingly, we can show it is also polynomial time solvable. First, one can see that maximizing is equivalent to minimize for some strictly convex increasing function , and range through all semi-matchings so each vertex in has degree exactly (Assuming it exists).
Apollonio and Sebő shown the following problem is polynomial time solvable .
Given a graph , a integer , convex functions for each , and an edge cost function . One can find the following in polynomial time.
It’s not hard to generalize it a bit further by requiring to respect some upper and lower bound on the vertices. Indeed, we can let , and set if is not between the upper and lower bounds.
Now, we are going to reduce the problem. The reduction is similar to the one for -or- matching.
For each vertex , split into two vertices and . Define . The new input graph consists of vertices . and connects to the same vertices as . We add an edge between and , with very large cost . Say . has both an upper and lower bound of . has a lower bound of . For each vertex in , add an upper and lower bound of . We have a strict convex function on each vertex .
Let , . We solve Problem 1 repeatedly for each from to .
Say there exists an optimal solution to the original problem with exactly vertices in with degree smaller than . Find the optimal solution to the new problem with . Let it be . We obtain from by identify pairs of vertices and . would be the solution to the original problem.
I first heard of the problem from , where they focused on case, but the reviewer can review more than one paper. This case can be handled easily. We can add degree upper and lower bounds to all vertices, and only look at subgraphs in that satisfies the upper and lower bounds. That is, we can also make sure no reviewers review too many papers too. Under that constraint, find lexicographically. This is possible but more tricky, as we have to do some reduction from capacitated -matching to -matching.
There is a little more generalization. Assume for each paper, we have a lower bound of reviews . That is, it has to be reviewed by at least person to be useful. So translating to the graph case, we can impose the constraint that or . One can see maximizing is equivalent to maximizing where for all vertices. Again, one can modify the reduction to handle the case when is either or .
 N.J.A. Harvey, R.E. Ladner, L. Lovász, T. Tamir, Semi-matchings for bipartite graphs and load balancing, Journal of Algorithms. 59 (2006) 53–78 10.1016/j.jalgor.2005.01.003.
 N. Apollonio, A. Sebő, Minconvex factors of prescribed size in graphs, SIAM Journal on Discrete Mathematics. 23 (2009) 1297–1310 10.1137/060651136.
 A. Yeşilçimen, E.A. Yildirim, An alternative polynomial-sized formulation and an optimization based heuristic for the reviewer assignment problem, European Journal of Operational Research. (2019) 10.1016/j.ejor.2019.01.035.