¿Se han estudiado algunas generalizaciones del peso máximo?

Por ejemplo, una forma de ver la coincidencia de peso máximo es que cada vértice obtiene una utilidad que es igual al peso del borde con el que coincide y cero en caso contrario.$v$$f_v= w(e_v)$

en consecuencia, una coincidencia de peso máximo podría verse como una maximización del objetivo .$\sum_v f_v$

¿Se han estudiado algunas generalizaciones de coincidencia de peso máximo que consideren funciones objetivas más generales utilizando ponderado, multivariado o no ?$f_v$

¿Se han estudiado otras variantes que son generalizaciones de una manera diferente?

¡Sírvanse proporcionar referencias si corresponde!

La coincidencia de peso máximo en es equivalente al conjunto independiente de peso máximo en el gráfico lineal de , y se puede escribir de la siguiente manera$G$$G$

Aquí es un vector de ocupaciones de vértices, devuelve 0 si x = y = 1, 1 si x = y = 0, de lo contrario el peso del nodo que no es 0. Se puede generalizar al permitir que otras opciones de y , por ejemplo,$\mathbf{x}\in\{0,1\}^n$$f_{ij}(x,y)$$\mathbb{x}$$f$

• La coloración adecuada más grande$\mathbf{x}\in \{1,\ldots,q\}^n, f(x,y)=\delta(x-y)$
• Modelo de estado fundamental$\mathbf{x}\in \{1,-1\}^n, f(x,y)=\exp(J x y)$

Si permite arbitraria no negativa , esto se convierte en el problema de encontrar la configuración más probable de variables en un campo aleatorio de Gibbs con represente potenciales de interacción de bordes. Generalizando más allá de las hipergrafías, su objetivo se convierte$f$$f$

Aquí es un conjunto de (tuplas de nodos), y es la restricción de a los nodos en la hiperedificación .$E$$x_e$$x$$e$

Ejemplo:

• Error al corregir la decodificación,$\mathbf{x} \in \{1,\ldots,q\}^n, f(x_e)=\exp{\text{parity} (x_e)}$
• Inferencia MAP en modelo de probabilidad estructurada de hipergrafía, arbitraria no negativa$f$

Generalizando en otra dirección, supongamos que en lugar de una sola coincidencia máxima, desea encontrar coincidencias máximas ponderadas más altas. Esta es una instancia especial de encontrar explicaciones más probables en un modelo probabilístico. El objetivo ahora se puede escribir como$m$$k$

Ver [ Flerova, 2010 ] para el significado del objetivo anterior.

De manera más general, en lugar de sort, o sobre reales, podemos considerar un semiremutativo conmutativo general donde y son operaciones abstractas que obedecen a la ley asociativa y distributiva. El objetivo que tenemos es ahora$\prod$$\max,\prod$$(\cdot,+)$$\cdot$$+$

Aquí, se toma sobre todos los bordes de alguna hipergrafía sobre nodos, se toma sobre -tuplas de valores, cada lleva 's a y forman un semi conmutativo -anillo$\bigotimes$$G$$n$$\bigoplus$$n$$f_e$$x$$E$$(\bigotimes,\bigoplus,E)$

Ejemplos:

• Función de partición de modelos de interacción de giro: use lugar de$(*,+)$$(\max,+)$
• Transformada rápida de Fourier sobre grupos abelianos: use grupos abelianos en lugar de$\mathbb{R}$

Lo que une todas estas generalizaciones es que el algoritmo más conocido para casos específicos del problema anterior es a menudo el mismo que el algoritmo más general, a veces llamado "Ley distributiva generalizada" [ Aji, 2000 ], que funciona en tiempo para hipergrafías del ancho de árbol acotado.$O(1)$

Esto pone la solución exacta de los problemas anteriores en un marco unificado, sin embargo, falta dicho marco para una solución aproximada (y quiero escucharlo si piensa lo contrario)

Hay varias extensiones del problema a estructuras más generales. Por ejemplo:

• Matroid Matching ( notas de clase , Matroid Matching y algunas aplicaciones , Matroid Matching: the Power of Local Search )

• Coincidencia de ruta ( problemas de coincidencia de ruta , coincidencia, matroides y extensiones )

• Coincidencia de hipergrafía (no se pueden encontrar buenas referencias)

En general, estas extensiones son NP-hard.

Una extensión interesante (aunque quizás sea bien conocida por usted) es la variante que permite la coincidencia parcial de vértices con otros vértices (en la configuración bipartita). Esta variante también se puede resolver usando el algoritmo húngaro, y se conoce como el problema de transporte (la métrica resultante se llama métrica de transporte, la distancia de movimiento de tierra , la distancia de Monge-Kantorovich-Wasserstein o la distancia de Mallows, dependiendo de quién usted pregunta).

Otro problema clásico que puede interpretarse como un problema de coincidencia con una extraña función objetivo es la coincidencia mínima máxima .$f_v$

Aquí puede definir siguiente manera: si no y está adyacente a otro nodo no coincidente; si coincide; y si no tiene coincidencia pero no está adyacente a ningún nodo no coincidente.$f_v$$0$$v$$n$$v$$n+1$$v$

Ahora el valor de la función objetivo es si la coincidente es máxima; de lo contrario es más pequeño que . Por lo tanto maximización sobre todos los resultados en la más pequeña máxima coincidencia .$\sum_v f_v$$n^2 + n - 2|M| \ge n^2$$M$$n^2$$\sum_v f_v$$M$$M$

Encontrar una coincidencia máxima más pequeña es un problema de optimización NP-hard, por lo que podemos decir con bastante seguridad que no es solo el problema habitual de coincidencia de peso máximo disfrazado. Nuevamente, tenga en cuenta que es "no local" en el sentido de que no es una función de restringida a los bordes incidentes con .$f_v$$M$$v$

Si desea algo que no se pueda reducir fácilmente al problema de igualación de peso máximo, aquí hay un ejemplo: el problema del matrimonio estable .

Una interpretación es que en el problema del matrimonio estable, es la "estabilidad" del vértice ; es si incide en un borde inestable (borde de bloqueo) y caso contrario. Entonces el objetivo es encontrar una coincidencia que maximice . (Y esto se puede resolver utilizando el algoritmo Gale – Shapley; lo óptimo es siempre .)$f_v$$v$$0$$v$$1$$\sum_v f_v$$|V|$

Una propiedad crucial de este es que depende no solo de qué bordes incidentes con coinciden, sino también de los vecinos de los bordes incidentes con .$f_v$$v$$v$

( Editar: la propiedad anterior es esencial para obtener algo que no sea solo el problema de coincidencia de peso máximo disfrazado. Tenga en cuenta que si las soluciones factibles son coincidencias y si solo depende de qué bordes coinciden con , entonces nosotros puede definir el peso de un borde siguiente manera: cuánto si reemplazamos una coincidencia vacía por una coincidencia que contiene solo el borde . Un peso máximo coincidente wrt estos pesos también maximiza .)$f_v$$v$$w(e)$$e = \{u,v\}$$f_u + f_v$$M = \emptyset$$M' = \{e\}$$e$$\sum_v f_v$

Muchas variantes y generalizaciones se consideran en el libro de Lovasz y Plummer .