Valori del vertice corrispondente con la somma dei pesi del bordo sul grafico bipartite

Question

All'inizio settimana ho chiesto Questa domanda (si prega di rivedere): < / P >.

.

Imagine Stackoverflow ha iniziato a offrire un abbonamento in cui le aziende potrebbe acquistare x numero di impressioni al mese per un set di tag.

Ad esempio, potresti essere interessato a eseguire un annuncio con 50000 Impressioni sui seguenti tags: javascipt, dattiloscritto, reagire, Nextjs, Nodejs, WebPack.

Stackoverflow "promette" otterrai 50000 impressioni, ma sono libero di distribuirli attraverso i tag sopra riportati, ma desiderano (potrebbe anche essere il 100% a un tag).

Una delle soluzioni fornite suggerito utilizzando l'algoritmo Hopcroft-Karp, che da allora ho potuto essere in grado di essere in grado di Implementare.

Tuttavia, sto avendo problemi a ridimensionare questa soluzione per funzionare per il mio caso d'uso. Il collo della bottiglia è in realtà nella configurazione del grafico in più - così rispetto alle prestazioni dell'algoritmo.

Il problema è il numero massiccio di bordi che devono essere inizializzati. Prendi l'esempio qui sotto:



==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 creiamo un vertice per rappresentare ogni unità, quindi finiremmo con un grafico che ha 101 bordi (7 * 11 + 4 * 6)!

Il problema che sto lavorando è ordinato di grandezza, quindi questo diventa rapidamente irrealistico.

Come suggerisci, posso ridurre il numero di vertice ridimensionando le unità, ma perdo risoluzione e questo è in qualche modo importante in questo caso (posso forse scalare di 100x max).

Stavo pensando che ci debba essere un modo più efficiente per farlo, poiché sto essenzialmente duplicando il vertice per ogni unità. Ho inventato il seguente grafico bipartite con bordi ponderati e valori vertice:

L'obiettivo sarebbe quello di regolare i pesi dei bordi in modo tale che:

.
• a sinistra, la somma dei bordi è uguale al valore del vertice
• A destra, la somma dei bordi è inferiore o uguale al valore del vertice

Di seguito è un esempio di una delle soluzioni:

Indovina (sperando) Questo è già un problema ben noto, per il quale c'è anche una soluzione ben documentata (idealmente quella che non è NP-HARD)!

Forse è anche possibile modificare l'algoritmo Hopcroft-Karp per lavorare per questo?

Answer 1

Ho cattive notizie. Non c'è speranza per un algoritmo il cui tempo di esecuzione del caso peggiore è polinomiale nella dimensione del grafico ponderato (a meno che P= NP, che sembra improbabile).

Il tuo problema è duro come il problema dello zaino, che non ha algoritmo polinomiale (a meno che P= NP) quando l'ingresso è rappresentato in binario. Il problema dello zaino ha un algoritmo di tempo pseudopolinomiale, il che significa che esiste un algoritmo il cui tempo di esecuzione è polinomiale nei numeri (ma non del tempo polinomiale nella dimensione dell'ingresso). Nella tua impostazione, che si trasformano in un algoritmo il cui tempo di esecuzione è polinomiale nella dimensione del grafico indeletato (con un numero massiccio di bordi) ma non polinomiale nella dimensione del grafico ponderato (con un piccolo numero di bordi).

È possibile provare a esprimere questo come un'istanza di programmazione lineare intere (ILP), quindi risolvi con un risolutore ILP. È possibile che potrebbe produrre una soluzione più efficiente. L'idea principale è quella di introdurre una variabile integer $ x_ {i, j} $ che conta il numero di impressioni fornite alla società $ i $ in tag $ j $ ; Quindi puoi introdurre alcune disuguaglianze lineari per catturare i requisiti del problema.