Earlier this week I asked this question (please review):
Imagine StackOverflow started offering a subscription where companies could buy X number of impressions per month for a set of tags.
For example, you might be interested in running an ad with 50000 impressions on the following tags: javascipt, typescript, react, nextjs, nodejs, webpack.
StackOverflow "promises" you will get 50000 impressions, but they are free to distribute them across the above tags however they desire (could even be 100% to one tag).
One of the solutions provided suggested using the Hopcroft-Karp algorithm, which I have since been able to successfully implement.
However, I'm having trouble scaling this solution to work for my use case. The bottle neck is actually in the setup of the graph more-so than the algorithm performance.
The problem is the massive number of edges that must be initialized. Take the example below:
==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
If we create a vertex to represent every unit, then we would end up with a graph that has 101 edges (7*11 + 4*6)!
The problem I'm working on is orders of magnitude larger, so this quickly becomes unrealistic.
As suggest, I can reduce the number of vertex by scaling the units, but I lose resolution and that's actually somewhat important in this case (I can maybe scale by 100x max).
I was thinking there must be a more efficient way to do this, since I'm essentially duplicating vertex for every unit. I came up with the following bipartite graph with weighted edges and vertex values:
The goal would be to to adjust the weights of the edges so that:
- On the left, the sum of edges is equal the value of the vertex
- On the right, the sum of edges is less than or equal to value of the vertex
Below is an example of one of the solutions:
I'm guessing (hoping) this is already a well known problem, for which there is also a well documented solution (ideally one that's not NP-hard)!
Maybe it's even possible to modify the Hopcroft-Karp algorithm to work for this?