2

我有一个匹配问题，我不知道如何解决它：

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;

max-matchings 是 5 和 9，所以 5 是答案。（所以配置是 s(a_0)=0）

4

1 回答 1

2

我怀疑这是作业，因为提问者使用的是他的真实姓名。

不幸的是，找到近似比优于 2 的状态分配（假设 Unique Games；否则为 1.3606）是NP-hard。令 G 为最小顶点覆盖的一个实例。集合 A 对 G 中的每个边都有一个顶点。集合 B 对 G 中的每个顶点都有一个顶点。如果对应于 a j的边的较小端点对应于，则令 w(a j , b k , 0 )为1 b k，否则为 0。关于更大的端点，类似地定义 w(a j , b k , 1)。这个实例的最小最大匹配的基数等于G的最小顶点覆盖，后一个问题很难近似。

在算法方面，我们可以用它的线性规划对偶来代替内部最大权重匹配问题，以最小化最小值。这里y j是a j对应的对偶变量，z k是b k对应的对偶变量。

最小 ∑<sub>jy j + ∑<sub>kz k

英石

∀j,k。y j + z k ≥ (1 - s(a j )) w(a j , b k , 0) + s(a j ) w(a j , b k , 1)

∀j。s(a j ) ∈ {0, 1}

∀j。y j ≥ 0

∀k。z k ≥ 0

这个公式是一个混合整数程序，可以通过现成的软件（例如，GNU 线性编程工具包）在没有太多人力的情况下对其进行攻击。它可能会或可能不会比蛮力更好。

于 2010-07-10T19:59:04.583 回答