algorithm - 对顶点度数进行约束的加权二分匹配

Question

我有一个问题，我可以将其概念化如下:

我们有一群 n 人。 m 子集代表他们的种族，如白人、西类牙裔、亚洲人等。给定这些人的任意组合，我想检查它是否是一个多元化的群体。

多元化群体是满足多个要求的群体，每个要求的形式为“该群体中至少有 Ki 人属于子集 Si”。这是棘手的部分，一个人只能用来满足一个要求。比如，您不能将他/她用于多个要求。

一个例子:

给定:

至少有两个来自西类牙裔的人 = {a,b,c}

至少两个亚洲人={a,d,e}

{a,c,d} 组是否多元化？

{a,c,d} 组并不多样化，因为您不能将a 算作西类牙裔和亚裔。但，{a,c,d,e,f} 组是多样化的，因为我们有两个西类牙裔 a 和 c 以及两个亚裔 d 和 e。

尝试:

这是分配问题的一个实例。工作是种族，我们可以根据要求规定尽可能多的种族。例如，如果我们需要两个西类牙裔，那么我们就放置两个西类牙裔工作。然而，只有一些人能够胜任一项特定的工作。

这是我目前的尝试:

我将构建一个二分图，一方面是人集 P，另一方面是种族集 S。如果他/她属于种族，我们将在一个人 p_i 和一个种族 S_i 之间放置一条边。现在，我们将修改图表，对于每个种族 S_i 将其复制 k_i 次(S_{i,1}, S_{i,2}, .. ., S_{i,k_i})。并相应地添加新边。找到这个图的最大匹配 M。

现在，将 S_{i,j} 合并为一个 S_i，这样您就拥有了一个多样化的群体。然而，最大匹配只是该问题的一种可能解决方案。我的问题是一个决策问题，我想检查给定的组是否是一个解决方案。

Answer 1

我认为这是 http://en.wikipedia.org/wiki/Assignment_problem 的一个实例，通常用分配人员工作来描述，因此在您的情况下，工作是“坐在那里看起来很白”或“坐在那里看起来是西类牙裔”。只有一些人有资格做任何特定的工作，而且他们一次只能做一项工作。

通常分配算法会最小化成本，但您可以只使用成本 0/成本 1 来表示“是否属于正确的种族群体”。

解决这个问题的一种方法是 http://en.wikipedia.org/wiki/Hungarian_algorithm .这通常是针对 worker 与工作一样多的情况提出的，但你总是可以发明虚拟工作或虚拟 worker ，所有与虚拟相关的成本都是相同的成本，因此用虚拟优化问题可以准确地重现相对如果您忽略对虚拟对象的分配，您将获得的成本顺序，因此在忽略虚拟对象之后，有虚拟对象的最优选择与没有虚拟对象的最优选择是相同的。