※ 引述《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/m.aspx?n=bbs/Prob_Solve/M.1544069553.A.E6A.html