Concordancia bipartita ponderada máxima, restricción: el orden de cada gráfico se conserva

Question

Digamos que tengo dos conjuntos: (n_1, n_2, ...) y (m_1, m_2, ...) y una coincidencia de función coincidente (n, m) que devuelve un valor de 0 a 1. quiero encontrar la correspondencia entre los dos conjuntos de tal manera que se cumplan las siguientes restricciones:

• Cada elemento debe tener como máximo 1 elemento emparejado en el conjunto opuesto.
• elementos coincidentes serán emparejados con un elemento postizo a un costo 1
• La suma de la función de concordancia cuando se aplica a todos los elementos es máxima
• Estoy teniendo problemas para expresar de manera formal, pero si se alinearon cada conjunto paralelo entre sí con su orden original y trazó una línea entre los elementos combinados, ninguna de las líneas se cruzaría. Ex. [n_1 < -> m_2, n_2 < -> m_3] es una asignación válida pero [n_1 < -> m_2, n_2 < -> m_1] no lo es.

(creo que los tres primeros son limitaciones que coinciden bipartitos ponderados estándar, pero yo les especificado en caso de que no he entendido juego bipartito ponderado)

Esto es relativamente sencillo que ver con una búsqueda exhaustiva en tiempo exponencial (con respecto al tamaño de los conjuntos), pero espero que exista una solución de tiempo polinomial (idealmente O ((| n | * | m |)^3) o mejor).

He buscado una cantidad justa en el "problema de asignación"/"concordancia bipartita ponderada" y he visto variaciones con diferentes restricciones, pero no encontré una que coincida o que pude reducir a una con este agregado restricción de ordenamiento ¿Tienes alguna idea sobre cómo podría resolver esto? ¿O tal vez una prueba aproximada de que no se puede resolver en tiempo polinomial (para mis propósitos, una reducción a NP-complete también funcionaría)?

Answer 1

Este problema se ha estudiado con el nombre "concordancia no cruzada de peso máximo". Hay un programa dinámico simple de tiempo cuadrático. Sea M (a, b) sea el valor de una adaptación óptima en n , ..., n _un y m , ..., m _b. Tenemos la recurrencia

M (0, b) = -b
M (a, 0) = -a
M (a, b) = max {M (a - 1, b - 1) + partido (a, b), M (a - 1, b) - 1, M (a, b - 1) - 1}.

Al rastrear las argmaxes, puede recuperar una solución óptima de su valor.

Si la coincidencia tiene significativamente menos que un número cuadrático de entradas mayor que -1, hay un algoritmo que se ejecuta en tiempo lineal en el número de entradas útiles (Khoo and Cong, A Fast Multilayer General Area Router for MCM Designs).