我有一个匹配的问题，我不知道如何解决：
Given a complete bipartite graph (A, B).
Each node a_i in A, has two states: s(a_i)=0 or s(a_i)=1
Weighted edges are declared as: w(a_i, b_j, s(a_i))
为状态设置一个配置，问题变成最大匹配。
目标是找到具有最小最大匹配的配置。
例子：
|A|=|B|=1
w(a_0, b_0, 0) = 5;
w(a_0, b_0, 1) = 9;
最大匹配数是5和9，所以答案是5。（所以配置是s（a_0）=0）
最佳答案
我怀疑这是家庭作业，因为提问者用的是他的真名。
不幸的是，找到具有比2好的近似比率的状态（假设唯一的游戏；否则为1.3606）是NP难的。设g为最小顶点覆盖的一个实例。集合A为G中的每个边都有一个顶点。集合B为G中的每个顶点都有一个顶点。如果对应于AJ的边的较小端点对应于BK，则让W（AJ，BK，0）为1，否则为0。定义w（aj，bk，1）与较大端点类似这个实例的最小最大匹配的基数等于G的最小顶点覆盖，并且后者的问题是难以近似的。
在算法前面，我们可以用线性规划对偶来代替内部最大权匹配问题，以使最小值最小化。这里yj是对应于aj的对偶变量，zk是对应于bk的对偶变量。
最小∑j yj+∑k zk
s.t.公司。
J，K.YJ+ZK≥（1-S（AJ））W（AJ，BK，0）+S（AJ）W（AJ，BK，1）
J.S（aj）∈{0，1}
j.yj≥0
k.zk≥0
这个公式是一个混合整数程序，它可以被现成的软件（例如gnu线性规划工具包）攻击而不需要太多人力。它可能比暴力好，也可能不比暴力好。