algorithm - 最小最大匹配问题

Question

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

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)

Answer 1

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

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

在算法方面，我们可以用其线性规划对偶代替内部最大权重匹配问题，以最小化最小值。这里y_j是a_j对应的对偶变量，z_k是b_k对应的对偶变量>.

min ∑_j y_j + ∑_k z_k

s.t.

∀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 线性编程工具包)对其进行攻击。它可能比蛮力更好，也可能不会。