algorithm - 具有相关顶点成本的二分选择

Question

我想我正在寻找一种可以在二部图中找到“最小”“选择”的算法。每个顶点都有一个关联的(整数)成本来选择它。我只能找到最小化所选集中顶点的数量 的算法，而不是成本。我以前认为我需要一个“匹配”，但实际上我只需要覆盖每条边的顶点子集......

我认为贪婪的解决方案行不通。假设我们的集合是A，B:

顶点 1,2,3 在 A 中，成本为 1。顶点 4 在 B 中，成本为 2。

解决方案是删除最昂贵的顶点，4。基于成本选择的贪婪解决方案将失败。同样，如果 B 的成本为 10，我们就不能贪婪地选择连接最紧密的顶点。

我想到了一个不同的措辞:“给定一个二分图，其中每个顶点都有相关成本，找到一个成本最低的顶点子集，使得每条边都与所选子集中的至少一个顶点相交”。

Answer 1

原始唱片:

min sum_v c_v x_v
s.t.
forall e=vw. x_v + x_w >= 1
forall v. x_v >= 0

双唱片:

max sum_e y_e
s.t.
forall v. sum_{e=vw} y_e <= c_v
forall e. y_e >= 0

1. 找到一个最小割，其中的边是从 A 到 B 的具有无限容量的弧，A 中的顶点是源，B 中的顶点是汇，所有顶点的容量都等于它们的成本。 (等效地，创建一个带有到 A 的弧的 super 源和一个带有来自 B 的弧的 super 接收器。)

2. 获取切割“汇”侧的 A 和“源”侧的 B。每条边 vw 都被覆盖了，因为如果 v 和 w 都不属于覆盖层，那么 vw 就是残差。

我想给 Jenő Egerváry 一个小费。