¿Complejidad del problema de matrimonio?

Supongamos que tienes hombres y mujeres. Cada persona tiene atributos. Cada persona indica un conjunto de atributos que debe tener un posible candidato. Una coincidencia es un conjunto de pares. Cada par une a un macho con una hembra. La satisfacción de una coincidencia es el número de atributos satisfechos para la persona menos afortunada. n $n$$n$$m$

¿Encontrar una coincidencia con la máxima satisfacción puede resolverse de manera eficiente o es duro?$NP$

Comencemos con la versión de decisión del problema: dado un "nivel de satisfacción" k, ¿existe una coincidencia en la que todos coincidan con una persona con al menos k atributos deseados? Esto es solo resolver coincidencias bipartitas en un gráfico donde conectamos un hombre y una mujer si cada uno obtiene satisfacción k del otro. (El tiempo de ejecución parece O (mn ^ 2).) Para obtener el problema original, simplemente realice una búsqueda binaria sobre k (para un factor log (m) adicional en el tiempo de ejecución).

Puede que haya entendido mal la pregunta, porque mi respuesta está en conflicto con la de Serge. Según tengo entendido, está preguntando sobre el problema de asignación de cuello de botella lineal. Se sabe que esto se resuelve en O (n ^ 2.5).

La fuente de información más completa es [1], aunque realmente no me gusta el estilo del libro. También hay un sitio web: http://www.assignmentproblems.com/linearBNAP.htm

EDITAR: Para aclarar, queremos una asignación tal que se minimice la ventaja con el costo máximo. El costo será el número máximo de atributos no asignados para el hombre o la mujer que coinciden.

EDIT2: Solo puedo ofrecer referencias del libro que cité. Tres de ellos son:

1. G. Carpaneto y P. Toth Algorithm para la solución del problema de asignación de cuellos de botella. Computación , 27: 179-187m 1981
2. U. Derigs. Estrategias alternativas para resolver problemas de asignación de cuellos de botella: análisis y resultados computacionales. Computación , 33: 95-106, 1984
3. U. Derigs y U. Zimmermann. Un método de ruta de aumento para resolver problemas de asignación de cuello de botella lineal. Computing , 19: 285-295, 1978

Debería intentar obtener el libro, ya que enumera algunos de los algoritmos disponibles.

[1] Problemas de asignación por Rainer Burkard, Mauro Dell'Amico, Silvano Martello

Como Tsuyoshi señala en un comentario a continuación, no hay razón para que una solución al problema tenga que ser una correspondencia estable. Entonces, el enfoque de esta respuesta probablemente no funcione; especialmente porque creo que la respuesta de Tomer es correcta.

Parece que su versión del problema del matrimonio es equivalente al problema de matrimonio estable de arrepentimiento mínimo con los lazos, donde todos clasifican a los miembros del otro sexo con posibles vínculos, y el objetivo es maximizar la "felicidad" mínima.

$N^{1-\epsilon}$$\epsilon > 0$$N$

[1]: David Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita: variantes difíciles del matrimonio estable. Theor Comput Sci. 276 (1-2): 261-279 (2002). Postprint .

¿No es esto solo una variación de la coincidencia bipartita máxima de costo mínimo? El peso para cada borde es igual al número de atributos satisfechos, y en lugar de encontrar la coincidencia máxima que le da la suma de peso más pequeña, desea uno para el que se maximiza el peso mínimo del borde.

Si esta comprensión es correcta, creo que un algoritmo de ruta de aumento similar a Busacker – Gowen [ 1 ] funcionaría. En lugar de encontrar siempre la ruta de aumento más barata (en términos de suma de peso), encontrará la mejor (maximizando el borde mínimo). Eso, nuevamente, debería ser factible con una ligera modificación a cualquier algoritmo estándar de ruta más corta (como el de Dijkstra, que se usa en la versión de Busacker-Gowen usando el ajuste de peso de Edmonds y Karp).

$O(v|E|\lg |V|)$$O(vn^2\lg n)$