※ 引述《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 解的。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 73.202.90.47 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1544069553.A.E6A.html