Re: [問題] Paper Assignment Problem

作者: FRAXIS (喔喔)   2018-12-06 12:12:29
※ 引述《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 解的。
作者: cutekid (可愛小孩子)   2018-12-06 12:25:00
大推(Y)
作者: suhorng ( )   2018-12-07 09:28:00
m(_ _)m
作者: s89162504 (阿本)   2018-12-07 13:48:00
從來沒想過網路流的general的問題 學習了
作者: Davidhu127 (船船_BTTO)   2017-02-12 12:20:00
感謝大大找出原問題的class,不過這樣的話,原問題還能reduce成s-t flow嗎?記得這題好像曾是交大考題
作者: FRAXIS (喔喔)   2017-02-12 12:50:00
交大 102 年的考題

Links booklink

Contact Us: admin [ a t ] ucptt.com