与相关顶点成本的二分选择

Question

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

我不认为贪婪的解决方案可以工作。假设我们的集合是A，B：

顶点1,2,3是在A和花费1. 顶点4是在B和已经花费2.

的解决方案是，以除去最昂贵的顶点4.根据成本选择的贪婪解决方案将失败。同样，如果B的成本为10，我们就不能贪婪地选择最连接的顶点。

我想到了另外一种措词：“给定一个二部图，其中每个顶点都有一个相关的成本，找到最小成本顶点的一个子集，使得每个边都入​​射到您选择的子集中的至少一个顶点。

Answer 1

原始LP：

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

双LP：

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

1. 查找最小切割，其中边缘是从A的弧与无限容量为B，所述的顶点是来源，并且B中的顶点是汇点，所有顶点的容量等于其成本。 （等效地，用弧形成超A源，用B形成超形成线）

2. 以“切”的“水槽”一侧和“源”一侧的B。每一条边vw都被覆盖，因为如果v和w都不属于封面，那么vw就是残差。

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