1

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

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

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

解决方案是删除最昂贵的顶点，4。基于成本选择的贪婪解决方案将失败。类似地，如果 B 的成本为 10，我们无法贪婪地选择连接最多的顶点。

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

4

1 回答 1

3

原始唱片：

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 的超级源和从 B 的弧的超级汇。）

  2. 以切割“汇”侧的 As 和“源”侧的 B 为例。每条边 vw 都被覆盖，因为如果 v 和 w 都不属于覆盖范围，那么 vw 将是残差的。

我想给 Jenő Egerváry 的帽子提示。

于 2013-04-06T13:25:08.887 回答