我有一个匹配问题,我不知道如何解决:
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 的状态分配(假设为 Unique Games;否则为 1.3606)是NP-hard。令 G 为最小顶点覆盖的实例。集合 A 对 G 中的每条边都有一个顶点。集合 B 对 G 中的每个顶点都有一个顶点。令 w(aj, bk, 0) 为如果对应于 aj 的边的较小端点对应于 bk,则为 1,否则为 0。类似地关于更大端点定义 w(aj, bk, 1)。该实例的最小最大匹配的基数等于G的最小顶点覆盖,后一问题难以近似。
在算法方面,我们可以用其线性规划对偶代替内部最大权重匹配问题,以最小化最小值。这里yj是aj对应的对偶变量,zk是bk对应的对偶变量>.
min ∑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 线性编程工具包)对其进行攻击。它可能比蛮力更好,也可能不会。
关于algorithm - 最小最大匹配问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3217364/