[問題] Paper Assignment Problem

[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 的方法也可以。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.202.90.47
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1543900456.A.C5B.html
推 suhorng: paper 跟 reviewer 建法一樣, 求完最大流看 paper 的邊
→ suhorng: 的剩餘容量, 這樣可行嗎?
推 sunflower304: 感覺這個目標式不能用LP解
推 sunflower304: 另外回一樓 是否會有求完最大流但paper沒被審到k2
→ sunflower304: 次的
推 suhorng: 因為 paper 跟源點 (或匯點) 每條邊上限 k2, 這樣應該就
→ suhorng: 不存在可行的指派法了
推 sunflower304: 不太懂為何會沒有可行解？
→ FRAXIS: 上限 k2 代表 paper 最多被 k2 個人審
→ FRAXIS: 但是題目是要求被 k2 個人審的 paper 數量最多
推 suhorng: 喔喔, 所以是要求被合法指派的 paper 數量最多?
→ suhorng: 不知有沒有影響, 那 paper 可以被審超過 k2 次嗎
→ suhorng: 啊沒看清楚 objective 抱歉
→ FRAXIS: paper 審超過 k2 次是沒差啊 但是我不覺得這樣會比較容易.
推 rrkqq: 直接套邊有上下界限制的網路流就好了吧
我修正了一下題目的敘述，這樣應該比較清楚。
設定網路流的下限是保證每個 paper 被審 k2 次，但是這問題是要讓
被審 k2 次的 paper 越多越好。
※ 編輯: FRAXIS (73.202.90.47), 12/05/2018 21:45:58