最小最大匹配问题

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; 

MAX-匹配数是5和9，所以图5是答案。 （这样的配置是S（A_0）= 0）

Answer 1

我怀疑，这是家庭作业，作为提问使用化名。

不幸的是，找到近似比好于2的状态的分配（假设为独特游戏;否则为1.3606）是NP-hard。设G是最小顶点覆盖的一个实例。集合A具有用于G的集B具有用于在G.设W每个顶点顶点的每一边缘顶点（一个_Ĵ，B _ķ，0）是1，如果对应于边缘中的较小者端点a _j对应于b _k，否则为0。定义W（A _Ĵ，B _ķ，1）同样地相对于所述更大的端点。这个实例的最小最大匹配的基数等于G的最小顶点覆盖，而后一个问题很难近似。

在算法前，我们可以通过它的线性规划双取代的内最大重匹配问题，从而最小以最小化。这里y _j是对应于 _j的双变量，并且z _k是对应于b _k的双变量。

分钟Σ_Ĵý_Ĵ +Σ_ķŽ_ķ

S.T.

∀j，k。 ÿ_Ĵ + Z _ķ≥（1 - S（一个_Ĵ））W（A _Ĵ，B _ķ，0）+ S（一个_Ĵ）W（A _Ĵ， b _ķ，1）

∀j。 s（a _j）ε{0,1}

∀j。 ÿ_Ĵ≥0

∀k。ž_ķ≥0

此制剂是混合整数程序，它可以无需太多人的努力通过现成的，现成的软件（例如，GNU线性规划工具集）被攻击。它可能会或可能不会比蛮力更好。