PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Paper Assignment Problem

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間5年前 (2018/12/06 12:12)推噓4(4推 0噓 2→)

留言6則, 5人參與討論串2/2 (看更多)

※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1544069553.A.E6A.html