最小最大匹配問題

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線性規劃工具集）被攻擊。它可能會或可能不會比蠻力更好。