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

[問題] Paper Assignment Problem

看板Prob_Solve (計算數學 Problem Solving)作者 (喔喔)時間6年前 (2018/12/04 13:14), 6年前編輯推噓7(7推 0噓 8→)
留言15則, 4人參與, 6年前最新討論串1/2 (看更多)
在 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
推
12/04 14:04, 6年前 , 1F
paper 跟 reviewer 建法一樣, 求完最大流看 paper 的邊
12/04 14:04, 1F
→
12/04 14:04, 6年前 , 2F
的剩餘容量, 這樣可行嗎?
12/04 14:04, 2F
推
12/04 14:40, 6年前 , 3F
感覺這個目標式不能用LP解
12/04 14:40, 3F
推
12/04 14:42, 6年前 , 4F
另外回一樓 是否會有求完最大流但paper沒被審到k2
12/04 14:42, 4F
→
12/04 14:42, 6年前 , 5F
次的
12/04 14:42, 5F
推
12/04 14:51, 6年前 , 6F
因為 paper 跟源點 (或匯點) 每條邊上限 k2, 這樣應該就
12/04 14:51, 6F
→
12/04 14:51, 6年前 , 7F
不存在可行的指派法了
12/04 14:51, 7F
推
12/04 15:48, 6年前 , 8F
不太懂為何會沒有可行解？
12/04 15:48, 8F
→
12/04 21:31, 6年前 , 9F
上限 k2 代表 paper 最多被 k2 個人審
12/04 21:31, 9F
→
12/04 21:31, 6年前 , 10F
但是題目是要求被 k2 個人審的 paper 數量最多
12/04 21:31, 10F
推
12/04 22:02, 6年前 , 11F
喔喔, 所以是要求被合法指派的 paper 數量最多?
12/04 22:02, 11F
→
12/04 22:03, 6年前 , 12F
不知有沒有影響, 那 paper 可以被審超過 k2 次嗎
12/04 22:03, 12F
→
12/04 22:04, 6年前 , 13F
啊沒看清楚 objective 抱歉
12/04 22:04, 13F
→
12/05 11:51, 6年前 , 14F
paper 審超過 k2 次是沒差啊 但是我不覺得這樣會比較容易.
12/05 11:51, 14F
推
12/05 12:23, 6年前 , 15F
直接套邊有上下界限制的網路流就好了吧
12/05 12:23, 15F
我修正了一下題目的敘述，這樣應該比較清楚。 設定網路流的下限是保證每個 paper 被審 k2 次，但是這問題是要讓 被審 k2 次的 paper 越多越好。 ※ 編輯: FRAXIS (73.202.90.47), 12/05/2018 21:45:58
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1S1WqenR (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1S1WqenR (Prob_Solve)