Valores de vértice a juego con la suma de pesos de borde en el gráfico bipartito

Question

A principios de esta semana, le pregunté a esta pregunta (por favor revisa): < / p>

Imagine StackOverFlow comenzó a ofrecer una suscripción donde las empresas podría comprar x número de impresiones por mes para un conjunto de etiquetas.

Por ejemplo, podría estar interesado en ejecutar un anuncio con 50000 Impresiones en las siguientes etiquetas: Javasctipt, Typescript, reaccionar, NEXTJS, NODEJS, WEBPACK.

StackOverFlow "promesas" obtendrás 50000 impresiones, pero son Libre de distribuirlos a través de las etiquetas anteriores, sin embargo, desean (Incluso podría ser 100% a una etiqueta).

Una de las soluciones proporcionadas sugirió usar el algoritmo Hopcroft-Karp, que desde entonces he podido exitosamente implementar.

Sin embargo, tengo problemas para escalar esta solución para trabajar para mi caso de uso. El cuello de la botella está en realidad en la configuración del gráfico más, por lo que el rendimiento del algoritmo.

El problema es el número masivo de bordes que deben inicializarse. Tome el siguiente ejemplo:



==Inventory==

Tag          Units 

javascipt    2 
typescript   4 
react        3 
nextjs       3   

== Subscriptions ==  

Account  Units   Tags
Acme     7       javacript, typescript, react, nextjs

Stark    4       javacript, typescript

Si creamos un vértice para representar cada unidad, entonces terminaríamos con un gráfico que tiene 101 bordes (7 * 11 + 4 * 6).

El problema en el que estoy trabajando es órdenes de magnitud más grande, por lo que esto rápidamente se vuelve poco realista.

Como sugieren, puedo reducir el número de vértices al escalar las unidades, pero pierdo la resolución y eso es en realidad algo importante en este caso (tal vez puedo escalar en 100x max).

Estaba pensando que debe haber una forma más eficiente de hacer esto, ya que esencialmente estoy duplicando el vértice para cada unidad. Me fui con el siguiente gráfico bipartito con bordes ponderados y valores de vértice:

El objetivo sería ajustar los pesos de los bordes para que:

• a la izquierda, la suma de los bordes es igual al valor del vértice
• a la derecha, la suma de los bordes es menor o igual que el valor del vértice

A continuación se muestra un ejemplo de una de las soluciones:

Estoy adivinando (con la esperanza) Este ya es un problema conocido, para el cual también hay una solución bien documentada (idealmente, ¡no es NP-HARD)!

¡Tal vez sea posible modificar el algoritmo Hopcroft-Karp para trabajar para esto?

Answer 1

Tengo malas noticias. No hay esperanza de un algoritmo cuyo peor tiempo de funcionamiento es polinomio en el tamaño del gráfico ponderado (a menos que p= NP, que parece poco probable).

Su problema es tan difícil como el problema de Knapsack, que no tiene algoritmo de tiempo polinomial (a menos que p= NP) cuando la entrada esté representada en binario. El problema de Knapsack tiene un algoritmo de tiempo pseudopolinómico, lo que significa que hay un algoritmo cuyo tiempo de funcionamiento es polinomio en los números (pero no el tiempo polinomial en el tamaño de la entrada). En su configuración, que se convierte en un algoritmo cuyo tiempo de funcionamiento es polinomial en el tamaño del gráfico no ponderado (con un número masivo de bordes) pero no polinomial en el tamaño del gráfico ponderado (con un pequeño número de bordes).

Podría intentar expresar esto como una instancia de programación lineal (ILP) de enteros, y luego resolver con un solucionador ILP. Es posible que pueda producir una solución más eficiente. La idea central es introducir una variable entera $ x_ {i, j} $ que cuenta el número de impresiones proporcionadas a la compañía $ i $ en la etiqueta $ j $ ; Luego, puede introducir algunas desigualdades lineales para capturar los requisitos del problema.