Valeurs de sommet correspondantes avec la somme des poids de bord sur le graphique bipartite

Question

Plus tôt cette semaine, j'ai demandé à Cette question (veuillez revoir): < / p>

Imagine Stackoverflow a commencé à offrir un abonnement où les entreprises pourrait acheter x nombre d'impressions par mois pour un ensemble de balises.

Par exemple, vous pourriez être intéressé à exécuter une annonce avec 50000 Impressions sur les balises suivantes: Javascipt, Typescript, React, NEXTJS, NODEJS, WebPack.

Stackoverflow "promet" Vous obtiendrez 50000 impressions, mais elles sont libre de les distribuer à travers les balises ci-dessus, mais ils désirent (pourrait même être 100% à une étiquette).

Une des solutions fournies suggérées à l'aide de l'algorithme HopCroft-Karp, que j'ai depuis pu réussir avec succès mettre en œuvre.

Cependant, j'ai des difficultés à réduire cette solution pour travailler pour mon cas d'utilisation. Le cou de la bouteille est en fait dans la configuration du graphique plus, donc que les performances d'algorithme.

Le problème est le nombre massif de bords qui doivent être initialisés. Prenez l'exemple ci-dessous:



==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 nous créons un sommet pour représenter chaque unité, nous vous retrouverons avec un graphique contenant 101 bords (7 * 11 + 4 * 6)!

Le problème que je travaille est des ordres de magnitude plus grande, de sorte que cela devient rapidement irréaliste.

Comme suggère, je peux réduire le nombre de sommets en modifiant les unités, mais je perds la résolution et c'est en fait un peu important dans ce cas (je peux peut-être échelle de 100x max).

Je pensais qu'il doit y avoir un moyen plus efficace de le faire, car je suis essentiellement dupliquant le sommet pour chaque unité. J'ai proposé le graphique bipartite suivant avec des bords pondérés et des valeurs de sommet:

L'objectif serait de régler les poids des bords afin que:

• à gauche, la somme des bords est égale à la valeur du sommet
• à droite, la somme des bords est inférieure ou égale à la valeur du sommet

ci-dessous est un exemple de l'une des solutions:

Je suppose que c'est déjà un problème bien connu, pour lequel il existe également une solution bien documentée (idéalement une personne qui n'est pas np-dur)!

Peut-être qu'il est même possible de modifier l'algorithme HopCroft-Karp pour y travailler?

Answer 1

J'ai de mauvaises nouvelles. Il n'y a aucun espoir d'un algorithme dont le temps de fonctionnement pire est polnomial de la taille du graphique pondéré (sauf si p= np, qui semble improbable).

Votre problème est aussi difficile que le problème du sac à dos, qui n'a aucun algorithme de temps polynomial (sauf si p= np) lorsque l'entrée est représentée en binaire. Le problème du knapsack a un algorithme de temps pseudopolynomial, ce qui signifie qu'il y a un algorithme dont le temps de fonctionnement est polynomial dans les nombres (mais pas de temps polynomial dans la taille de l'entrée). Dans votre réglage, cela se transforme en algorithme dont le temps d'exécution est polnomial de la taille du graphique non pondéré (avec un nombre massif de bords) mais non polynomial dans la taille du graphique pondéré (avec un petit nombre de bords).

Vous pouvez essayer d'exprimer cela comme une instance de programmation linéaire entière (ILP), puis résolve avec un solveur ILP. Il est possible que cela produise une solution plus efficace. L'idée principale est d'introduire une variable entière $ x_ {i, j} $ qui compte le nombre d'impressions fournies à la société $ i $ dans la balise $ j $ ; Ensuite, vous pouvez introduire quelques inégalités linéaires pour capturer les exigences du problème.