Min Max-assorti Problème

Question

J'ai un problème de correspondance et je ne sais pas comment le résoudre:

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)) 

Fixation d'une configuration pour les états, le problème devient une correspondance max.

L'objectif est de trouver la configuration avec un minimum de correspondance maximale.

Exemple:

|A|=|B|=1 
w(a_0, b_0, 0) = 5; 
w(a_0, b_0, 1) = 9; 

max-appariements sont 5 et 9, de sorte que la figure 5 est la réponse. (donc la configuration est s (a_0) = 0)

Answer 1

Je doute que ce soit des devoirs, puisque le questionneur utilise son vrai nom.

Malheureusement, trouver une affectation d'états avec un rapport d'approximation supérieur à 2 (en supposant que Jeux uniques, 1.3606 sinon) est NP-difficile. Soit G une instance de couverture vertex minimale. L'ensemble A a un sommet pour chaque arête dans G. L'ensemble B a un sommet pour chaque sommet dans G. Soit w (un _j, b _k, 0) être 1 si l'extrémité inférieure du bord correspondant à un _j correspond à b _k, et 0 sinon. Définir w (un _j, b _k, 1) de manière similaire par rapport au point final supérieur. La correspondance maximale minimale de cette instance a une cardinalité égale à la couverture de sommet minimale de G, et ce dernier problème est difficile à approximer. Sur le front des algorithmes, nous pouvons remplacer le problème interne de l'appariement du poids maximum par son dual de programmation linéaire afin de minimiser le minimum. Ici y _j est la variable correspondant à une double _j et z _k est la variable double correspondant à 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 (un _j) ∈ {0, 1}

∀j. y _j ≥ 0

∀k.z _{k ≥ 0}

Cette formulation est un programme entier mixte, qui peut être attaqué sans trop d'effort humain par le logiciel hors de l'étagère (par exemple, le kit de programmation linéaire GNU). Cela peut ou peut ne pas être meilleur que la force brute.