# Matching vertex values with sum of edge weights on bipartite graph

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?

• someone please fix my title... I don't really know the correct terminology to explain the problem. – NSjonas Apr 1 '20 at 6:38

You could try expressing this as an integer linear programming (ILP) instance, and then solve with an ILP solver. It's possible that might yield a more efficient solution. The core idea is to introduce an integer variable $$x_{i,j}$$ that counts the number of impressions provided to company $$i$$ in tag $$j$$; then you can introduce a few linear inequalities to capture the problem's requirements.