Complexité du problème d'adoption de chaton

Cela s'est produit alors que j'essayais de répondre à cette question sur la minimisation de la longueur de câblage . J'allais appeler cela le problème du "mariage polygame", mais Internet, donc les chatons. Yay!

Supposons que nous ayons $M$ chatons qui doivent être adoptées par personnes, . Pour chaque chaton, et chaque personne il y a un coût . Nous aimerions minimiser le coût total de l'adoption de tous les chatons. Il existe également un ensemble de contraintes: chaque personne ne peut pas adopter plus de chatons.$N$$M > N$$i$$j$$c_{ij}$$j$$u_j$

Sans les contraintes, le problème est facile; chaque chaton va avec la personne pour laquelle est minime. Avec les contraintes existe-t-il un algorithme efficace pour ce problème ou est-il NP-difficile?$i$$j$$c_{ij}$

Il s'agit du problème de débit min-coût max.

Considérons un graphique , où A est l'ensemble des chatons, B est l'ensemble des personnes.$G=(A\cup B\cup \{s,t\},E)$$A$$B$

Soit la capacité des arêtes, et c : E → R + le coût d'une arête. Nous nous assurons que$C:E\to \mathbb{R}^+$$c:E\to \mathbb{R^+}$

1. Il y a un bord entre , où a i ∈ A et b j ∈ B , et C ( a i , b j ) = 1 , c ( a i , b j ) = c i , j .$a_i,b_j$$a_i\in A$$b_j\in B$$C(a_i,b_j)=1$$c(a_i,b_j)=c_{i,j}$
2. Il y a un bord entre et a i ∈ A , et C ( s , a i ) = 1 , c ( s , a i ) = 0 .$s$$a_i\in A$$C(s,a_i)=1$$c(s,a_i)=0$
3. Il y a un bord entre et t , et C ( b j , t ) = u j , c ( b j , t ) = 0 .$b_j\in B$$t$$C(b_j,t)=u_j$$c(b_j,t)=0$

Si le débit max est , alors nous savons qu'il existe une solution. Vous pouvez construire une solution à coût min à partir du flux max à coût min.$M$

Il s'agit du problème d'appariement parfait du poids minimum qui est polynomial. Considérons le graphe bipartite complet , dans lequel L contient un nœud l i pour chaque chaton i , R se compose de u j copies du nœud r j pour chaque personne j , et les bords e i j ∈ E entre l i et chaque copie de r j , avec les poids c i j .$(L , R , E)$$L$$l_i$$i$$R$$u_j$$r_{j}$$j$$e_{ij} \in E$$l_i$$r_{j}$$c_{ij}$

Nous savons que sinon, tous les chatons ne peuvent pas être affectés à des personnes.$|L| \leq |R|$

Depuis parfaite adéquation doit correspondre à tous les nœuds, il faut ajouter des nœuds fictifs à (pour obtenir | L | = | R | ) et les connecter avec zéro bords de poids à tous les noeuds R .$L$$|L| = |R|$$R$

Il est peut-être intéressant d'observer que l'on peut réduire la partition à une variante de ce problème. Étant donné est une instance de Partition avec les éléments avec q même parmi lesquels nous devons choisir un sous-ensemble S ⊆ { 1 , … , q } avec | S | = q / 2 tel que ∑ i ∈ S x i = ∑ i ∉ S x i = $\{x_1,\dots,x_q\}$$q$$S \subseteq \{1,\dots,q\}$$|S|=q/2$$\sum_{i\in S} x_i = \sum_{i\not\in S} x_i = K$. (Notez que l'exigence de choisir exactement la moitié des éléments n'est pas la forme habituelle mais cette forme est toujours NP-difficile.) Soit chaque chaton un élément de l'ensemble; qu'il y ait deux personnes; soit les poids et c i 2 = - x i ; soit u 1 = u 2 = q / 2 . Ensuite, cette instance de Kitten Adoption a un maximum de 0 si l'instance de Partition a une solution.$c_{i1} = x_i$$c_{i2} = -x_i$$u_1 = u_2 = q/2$$0$

If the costs in Kitten Adoption are meant to always be positive then one can just add a large enough constant $C$ to all weights to ensure they are the right sign, when the required threshold is $Cq$ instead of 0.

I am not sure what this says about the complexity of the original problem, but given the often-seen "one of minimize/maximize is NP-hard, the other is in P" setup for combinatorial optimization problems, I would start looking for an efficient algorithm.