# 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. Apr 1, 2020 at 6:38

I've got bad news. There's no hope for an algorithm whose worst-case running time is polynomial in the size of the weighted graph (unless P = NP, which seems unlikely).

Your problem is as hard as the knapsack problem, which has no polynomial-time algorithm (unless P = NP) when the input is represented in binary. The knapsack problem has a pseudopolynomial time algorithm, which means that there is an algorithm whose running time is polynomial in the numbers (but not polynomial-time in the size of the input). In your setting, that turns into an algorithm whose running time is polynomial in the size of the unweighted graph (with a massive number of edges) but not polynomial in the size of the weighted graph (with a small number of edges).

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.

• If you had to use a language that doesn't have an existing ILP solver, would it be realistic for someone with a modest (at best) background in mathematics to come up with solution? I spent some time looking at ILP before H-K, but didn't even know where to start. Apr 1, 2020 at 14:55
• @NSjonas, I don't think the programming language will make much of a difference. Most ILP solvers have a text-based interface you can use. There are resources on using ILP to solve problems; e.g., faculty.nps.edu/dell/docs/Formulettes060425.pdf.
– D.W.
Apr 1, 2020 at 15:58
• First sentence: "The art of formulating linear and integer linear programs is, well, an art: It is hard to teach, and even harder to learn". I'm screwed :) Apr 1, 2020 at 16:05
• @NSjonas, naah, it shouldn't be too bad; see edited answer for a suggestion on how to get started.
– D.W.
Apr 1, 2020 at 16:08