I'm trying to classify and come up with a reasonable solution for the following problem (abstracted from a real world problem).
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).
How should StackOverflow optimize the distribution so that they can sell/deliver the maximum number of impressions?
For simplicity, assume:
- we know the number of impressions each tag receives per month ahead of time and it doesn't change
- each impressions only belongs to a single tag
The simplest way to approach this is with a "first-fit" (or maybe better described as "first come, first-serve") algorithm:
- Get all active "subscriptions" (impressions & tags), ordered by Created Date ASC
- For each "subscription", grab the first tag and "consume" as many impressions as we can. If the subscription still has remaining impressions, move to the next tag.
- Repeat with next subscription
That might play out something like this:
==Inventory== Tag Impressions javascipt 2000 typescript 5000 react 5000 nextjs 5000 == Subscriptions == Acme: 8000 (javacript, typescript, react, nextjs) Stark: 5000 (javacript, typescript) == Allocation Results == Acme: - javacript: 2000 - typescript: 5000 - react: 1000 Stark: - javacript: 0 - typescript: 0
The optimization for this solution is clearly horrible. In the example above, while we had more than enough impressions to go around, we allocated the only ones that "Stark" could purchase before we got around to them.
Is there an official name to this problem and what does the optimal solution look like?