作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] Paper Assignment Problem
时间Tue Dec 4 13:14:14 2018
在 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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1543900456.A.C5B.html
1F：推 suhorng: paper 跟 reviewer 建法一样, 求完最大流看 paper 的边 12/04 14:04
2F：→ suhorng: 的剩余容量, 这样可行吗? 12/04 14:04
3F：推 sunflower304: 感觉这个目标式不能用LP解 12/04 14:40
4F：推 sunflower304: 另外回一楼 是否会有求完最大流但paper没被审到k2 12/04 14:42
5F：→ sunflower304: 次的 12/04 14:42
6F：推 suhorng: 因为 paper 跟源点 (或汇点) 每条边上限 k2, 这样应该就 12/04 14:51
7F：→ suhorng: 不存在可行的指派法了 12/04 14:51
8F：推 sunflower304: 不太懂为何会没有可行解？ 12/04 15:48
9F：→ FRAXIS: 上限 k2 代表 paper 最多被 k2 个人审 12/04 21:31
10F：→ FRAXIS: 但是题目是要求被 k2 个人审的 paper 数量最多 12/04 21:31
11F：推 suhorng: 喔喔, 所以是要求被合法指派的 paper 数量最多? 12/04 22:02
12F：→ suhorng: 不知有没有影响, 那 paper 可以被审超过 k2 次吗 12/04 22:03
13F：→ suhorng: 啊没看清楚 objective 抱歉 12/04 22:04
14F：→ FRAXIS: paper 审超过 k2 次是没差啊 但是我不觉得这样会比较容易. 12/05 11:51
15F：推 rrkqq: 直接套边有上下界限制的网路流就好了吧 12/05 12:23
我修正了一下题目的叙述，这样应该比较清楚。
设定网路流的下限是保证每个 paper 被审 k2 次，但是这问题是要让
被审 k2 次的 paper 越多越好。
※ 编辑: FRAXIS (73.202.90.47), 12/05/2018 21:45:58