Complejidad del problema de adopción de gatitos

Esto surgió mientras intentaba responder esta pregunta sobre la minimización de la longitud del cableado . Iba a llamar a esto el problema del "matrimonio polígamo", pero Internet, así que gatitos. ¡Hurra!

Supongamos que tenemos gatitos que necesitan ser adoptados por N personas, M > N . Para cada gatito, i y cada persona j hay un costo c i j . Nos gustaría minimizar el costo total de adoptar a todos los gatitos. También hay un conjunto de restricciones: cada persona j no puede adoptar más que u j gatitos.$M$$N$$M > N$$i$$j$$c_{ij}$$j$$u_j$

Sin las restricciones, el problema es fácil; cada gatito va con la persona j para la cual c i j es mínimo. Con las restricciones, ¿existe un algoritmo eficiente para este problema o es NP-hard?$i$$j$$c_{ij}$

Este es el problema de flujo mínimo de costo mínimo.

Considere un gráfico , donde A es el conjunto de gatitos, $G=(A\cup B\cup \{s,t\},E)$$A$$B$ es el conjunto de personas.

Sea la capacidad de los bordes, y c : E → R $C:E\to \mathbb{R}^+$$c:E\to \mathbb{R^+}$ el costo de un borde. Nos aseguramos de que

1. Hay un borde entre , donde a i ∈ A y b j ∈ B , y C ( a i , b j ) = 1 , c ( a i , b j ) = c i , $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. Hay una arista entre y a i ∈ A , y C ( s , a i ) = 1 , c ( s , a i ) = $s$$a_i\in A$$C(s,a_i)=1$$c(s,a_i)=0$ .
3. Hay un borde entre y T , y C ( b j , t ) = u j , c ( b j , t ) = $b_j\in B$$t$$C(b_j,t)=u_j$$c(b_j,t)=0$ .

Si el flujo máximo es , entonces sabemos que existe una solución. Puede construir una solución de costo mínimo a partir del flujo máximo de costo mínimo.$M$

Este es el problema de coincidencia perfecta de peso mínimo que es polinómico. Considere el gráfico bipartito completo , en el que L contiene un nodo l i para cada gatito i , R consiste en u j copias del nodo r j para cada persona j , y los bordes e i j ∈ E entre l i y cada copia de r j , con pesos c i $(L , R , E)$$L$$l_i$$i$$R$$u_j$$r_{j}$$j$$e_{ij} \in E$$l_i$$r_{j}$$c_{ij}$ .

Sabemos que de lo contrario, no todos los gatitos pueden asignarse a personas.$|L| \leq |R|$

Desde coincidencia perfecta debe coincidir con todos los nodos, tenemos que añadir nodos ficticios a (para obtener | L | = | R | ) y conectarlos con cero bordes peso a todos los nodos en R .$L$$|L| = |R|$$R$

Posiblemente de interés es la observación de que uno puede reducir la Partición a una variante de este problema. Dado es una instancia de Partición con elementos con q incluso de los cuales tenemos que elegir un subconjunto S ⊆ { 1 , ... , q } con | S | = q / 2 tal 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$. (Tenga en cuenta que el requisito de elegir exactamente la mitad de los elementos no es la forma habitual, pero esta forma sigue siendo NP-hard). Deje que cada gatito sea un elemento del conjunto; que haya dos personas; dejemos que los pesos sean y c i 2 = - x i ; sea u 1 = u 2 = q / 2 . Entonces, esta instancia de Adopción de gatitos tiene un máximo de 0 si la instancia de Partición tiene una solución.$c_{i1} = x_i$$c_{i2} = -x_i$$u_1 = u_2 = q/2$$0$

Si los costos en Adopción de gatitos están destinados a ser siempre positivos, entonces se puede agregar una constante lo suficientemente grande a todos los pesos para garantizar que sean el signo correcto, cuando el umbral requerido es C q en lugar de 0.$C$$Cq$

No estoy seguro de lo que esto dice sobre la complejidad del problema original, pero dado que a menudo se ve "uno de minimizar / maximizar es NP-hard, el otro está en P" para problemas de optimización combinatoria, comenzaría a buscar un Algoritmo eficiente.