Correspondência de valores de vértices com soma dos pesos das arestas no gráfico bipartido

Question

No início desta semana eu perguntei essa questão (por favor revise):

Imagine StackOverflow começou a oferecer uma assinatura onde as empresas poderiam comprar x número de impressões por mês para um conjunto de tags.

Por exemplo, você pode estar interessado em executar um anúncio com 50000 impressões nas seguintes tags:Javascipt, TypeScript, React, NextJs, NodeJS, Webpack.

O Stackoverflow "promessas", você receberá 50000 impressões, mas elas são livres para distribuí -las pelas tags acima, como desejarem (pode até ser 100% a uma etiqueta).

Uma das soluções fornecidas sugeri usar o algoritmo Hopcroft-Karp, que desde então consegui implementar com sucesso.

No entanto, estou tendo problemas para dimensionar essa solução para funcionar no meu caso de uso.O gargalo está, na verdade, mais na configuração do gráfico do que no desempenho do algoritmo.

O problema é o grande número de arestas que devem ser inicializadas.Veja o exemplo abaixo:



==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

Se criarmos um vértice para representar cada unidade, terminaremos com um gráfico que possui 101 arestas (7*11 + 4*6)!

O problema no qual estou trabalhando é muito maior, então isso rapidamente se torna irrealista.

Como sugerido, posso reduzir o número de vértices dimensionando as unidades, mas perco a resolução e isso é realmente importante neste caso (talvez eu possa dimensionar em 100x no máximo).

Eu estava pensando que deveria haver uma maneira mais eficiente de fazer isso, já que estou essencialmente duplicando o vértice para cada unidade.Eu criei o seguinte gráfico bipartido com arestas ponderadas e valores de vértices:

O objetivo seria ajustar os pesos das arestas para que:

• À esquerda, a soma das arestas é igual ao valor do vértice
• À direita, a soma das arestas é menor ou igual ao valor do vértice

Abaixo está um exemplo de uma das soluções:

Suponho (espero) que este já seja um problema bem conhecido, para o qual também existe uma solução bem documentada (de preferência uma que não seja NP-difícil)!

Talvez seja possível modificar o algoritmo Hopcroft-Karp para funcionar para isso?

Answer 1

Tenho más notícias.Não há esperança para um algoritmo cujo tempo de execução no pior caso seja polinomial no tamanho do gráfico ponderado (a menos que P = NP, o que parece improvável).

Seu problema é tão difícil quanto o problema da mochila, que não possui algoritmo de tempo polinomial (a menos que P = NP) quando a entrada é representada em binário.O problema da mochila possui um algoritmo de tempo pseudopolinomial, o que significa que existe um algoritmo cujo tempo de execução é polinomial nos números (mas não em tempo polinomial no tamanho da entrada).Na sua configuração, isso se transforma em um algoritmo cujo tempo de execução é polinomial no tamanho do gráfico não ponderado (com um grande número de arestas), mas não polinomial no tamanho do gráfico ponderado (com um pequeno número de arestas).

Você poderia tentar expressar isso como uma instância de programação linear inteira (ILP) e depois resolver com um solucionador de ILP.É possível que isso resulte em uma solução mais eficiente.A ideia central é introduzir uma variável inteira $x_{i,j}$ que conta o número de impressões fornecidas à empresa $i$ na etiqueta $j$;então você pode introduzir algumas desigualdades lineares para capturar os requisitos do problema.