简单的任务分配问题

Question

我有一个简单的“分配”问题：

我们有一组代理$ a = {a_1，a_2， dotso，a_n } $和一组任务$ t = {t_1，t_1，t_2， dotso，t_m } $。请注意，$ m $不一定等于$ n $。与Wikipedia中的一般分配公式不同，任务$ T_C $只能根据任务的首选代理$ TA_C subseteq a $分配给代理。例如，如果我们有$ ta_1 = {a_1，a_3 } $，则意味着只能将任务$ t_1 $分配给$ a_1 $或$ a_3 $。现在，每个代理$ t_d $都有一个配额$ q_d $，其中$ q_d $是正整数。这意味着必须使用$ q_d $的任务数来分配$ a_d $。

问题

上面给出和一组配额$ {q_1，q_2， dotso，q_n } $，是否有任务分配给代理商，以使所有代理都符合其各自的配额$ q $。请注意，不一定将所有任务分配给代理。

可能的解决方案

我试图根据两分图$ g（a，t，e = cup ta_c）$进行重新制定此问题，并表示为匹配问题的一种形式，其中给定匹配的$ m $，一个顶点代理$ a_d in A中$匹配到$ q_d $ times，或者被事件与$ m $中的$ q_d $ edges相匹配，但是$ t $中的顶点是$ m $中的一个边缘。不太喜欢通常的匹配问题，这要求$ m $中的边缘是成对的不可变的。

但是，有人建议通过将代理$ a_d $复制到$ q_d $ vertices中，并以不同的方式将其作为不同顶点作为匹配算法的输入。边缘$ e $的集合也进行了相应的修改。将修改图称为$ g'$

从Graph $ G'$中可以拥有超过1个最大匹配项。现在，如果我正确理解这一点，我仍然必须检查每个最大的最大匹配，并看到其中至少一个满足每个$ agent $的$ qouta $约束，以实际提供解决问题的解决方案。

现在，我想证明，在满足问题的$ qouta $限制的图形$ g'$的所有最大匹配中，找不到一个最大匹配$ m $ 问题实例，否则存在解决方案，即$ M $。

我想证明该算法始终给出正确的结果。

问题

您能否与我分享一些关于我如何展示这一点的直觉？

Answer 1

正如我在CSTHORE帖子上所说的那样，这是通过最大匹配来解决的。以下内容应给出足够的直觉，以表明每个代理$ a_i $都有$ q_i $ - 如果转换的图形$ g'$具有匹配。首先，构造图形$ g $。现在，对于每个代理$ a_i $和配额$ q_i $，制作一个新的图$ g'$，其中$ q_i $副本为$ a_i $。也就是说，如果代理$ a_i $具有配额$ q_i = 3 $，则使2个新节点$ a_i'，a_i''$具有与$ a_0 $相同的任务。

这是可以提供帮助的插图。假设我们有完整的两部分图$ k_ {2,3} $，其中代理$ q_1 = 2，q_2 = 1 $。

原始图形$ g $，修改图$ g'$：

我们看到代理$ a_1 $在新图中有两个副本$ g'$，而代理$ a_2 $仅维护他的唯一副本。在$ g'$中求解最大匹配，然后将代理的所有副本合并到原件，您将拥有最好的作业。由于边缘未加权，因此一种可能的解决方案是（并合并的解决方案）：