※ 引述《FRAXIS (喔喔)》之铭言：
: 在 Grad-ProbAsk 版看到的问题。
: 给定 n 篇 paper 和 m 个 reviewer，
: Reviewer 不是每篇 paper 都可以审，
: 可以审查的关系用一集合
: R = {(reviewer, paper) | 此 reviewer 可以审该 paper} 表示。
: Chairman 要指派 paper 给 reviewer，每个 reviewer 最多
: 只能审 k1 篇 paper。
: objective: 最大化被 k2 个 reviewer 审过的 paper 数量
: 看起来很像是 network flow，但是 objective 该怎么用 network flow 表示？
: 如果有其他 min-cost flow/linear programming 的方法也可以。
我看了一些资料，发现已经有人研究过更一般化的 matching 问题。
针对一个图 G = (V, E)，
Matching 是找出 E 的一个子集 M ，使得每个点在 M 中的 degree 满足限制。
最常见的 matching 就是要找出 M 使得每个点在 M 中的 degree 是 1。
一种一般化的形式是，给定一个整数 b ，找出 M 使得每个点在 M 中
的 degree 不超过 b 。这种 matching 称为 b-matching。
更一般的形式是，给定两个整数 a 和 b ，找出 M 使得每个点在 M 中
的 degree 介于a 和 b 之间，这种 matching 称为 [a, b]-matching ，
所以常见的 matching 又可以称为 [1, 1] matching。
另一种一般化的定义是，给定一个函数 f: V -> 正整数，找出 M 使得
每个点 x 在 M 中的 degree <= f(x)。这种 matching 称为 f-matching。
再更一般个定义是，给定两个函数 f, g: V-> 正整数，找出 M 使得每
个点 x 在 M 中的 degree 介于 g(x) 和 f(x) 之间。这种 matching
称为 (g, f)-matching。
最后一种定义是，给定一个函数 B: V -> {0, .. |V|} 的子集，找出 M
使得每个点 x 在 M 中的 degree 被 B(x) 包含。这种 matching 称为
B-matching。
不同教科书可能会给这些 matching 不同名字，不过定义差不多都是这样。
除了找 feasible matching 之外，也有人研究 maximum cardinality matching，
或是 maximum weghted matching 。
原本的问题可以写成 B-matching 的形式：
令一二分图 G = (X union Y, R)来表示 reviewer (X) 和 paper (Y) 的关系。
所有 X 中的顶点 x，设定 B(x) = {0, ..., k1}，
所有 Y 中的顶点 y ，设定 B(y) = {0, k2}，
而我们要找的就是 maximum cardinality B-matching。
不过 Lovasz 已经证明了，就算输入是二分图，就算 X 中的 B 都是 {1}，
Y 中的 B 都是 {0, 3} ，找出 feasible B-matching 已经是 NPC 问题。
(The factorization of graphs. II https://doi.org/10.1007/BF01889919)
另一方面，对于 general graph ，只要 B 没有包含 > 1 的 gap
（亦即如果 i 不在 B(x) 中，那 i + 1 必在 B(x) 中），maximum cardinality
B-matching 是有 polynomial time 的解法。
(Optimal General Matchings https://doi.org/10.1007/978-3-030-00256-5_15)
也就是说，原本问题在 k2 = 2 时是可以有 polynomial time 解的。