Algoritmo de Otimização de Distribuição

Question

Estou tentando classificar e encontrar uma solução razoável para o seguinte problema (abstraído de um problema do mundo real).

Problema

Imagine que o StackOverflow começou a oferecer uma assinatura onde as empresas poderiam comprar um número X de impressões por mês para um conjunto de tags.

Por exemplo, você pode estar interessado em veicular um anúncio com 50.000 impressões nas seguintes tags: javascipt, typescript, react, nextjs, nodejs, webpack.

StackOverflow "promete" que você obterá 50.000 impressões, mas eles são livres para distribuí-las pelas tags acima da maneira que desejarem (pode até ser 100% para uma tag).

Como o StackOverflow deve otimizar a distribuição para que possam vender/entregar o número máximo de impressões?

Para simplificar, suponha:

• sabemos antecipadamente o número de impressões que cada tag recebe por mês e isso não muda
• cada impressão pertence apenas a uma única tag

Minha pesquisa

Acredito que isso possa ser semelhante ao Mochila ou Embalagem de lixo problemas.

A maneira mais simples de abordar isso é com um algoritmo de "primeiro ajuste" (ou talvez melhor descrito como "primeiro a chegar, primeiro a servir"):

1. Obtenha todas as "assinaturas" ativas (impressões e tags), ordenadas por data de criação ASC
2. Para cada “assinatura”, pegue a primeira tag e “consumir” o máximo de impressões que pudermos.Se a assinatura ainda tiver impressões restantes, passe para a próxima tag.
3. Repita com a próxima assinatura

Isso pode acontecer algo assim:

==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

A otimização para esta solução é claramente horrível.No exemplo acima, embora tivéssemos impressões mais do que suficientes, alocamos as únicas que "Stark" poderia comprar antes de chegarmos a elas.

Existe um nome oficial para este problema e como é a solução ideal?

Answer 1

Eu acho que isso é na verdade "apenas" correspondência bipartida de cardinalidade máxima, que pode ser resolvida de forma otimizada em $O(|E|\sqrt{|V|})$ tempo usando o Algoritmo Hopcroft-Karp.

De um lado, você tem um vértice para cada impressão exigida (digamos, o cliente A exige 50.000 de "javascript" ou "typescript" e o cliente B exige 10.000 "javascript", ou seja, 60.000 vértices no total) e, do outro lado, você tem um vértice para cada impressão fornecida (digamos, 30.000 rotulados como "javascript" e 15.000 rotulados como "datilografado", ou seja, 45.000 vértices no total).Desenhe uma aresta de cada impressão exigida para cada impressão fornecida de um tipo que satisfaça suas restrições de tipo de impressão (de modo que haveria 45.000 arestas saindo de cada um dos vértices do cliente A e 15.000 arestas saindo de cada um dos clientes B) e resolva.

Se você tiver milhares de impressões, poderá acabar com milhões de bordas, o que pode demorar muito.Se uma resposta aproximada for suficiente, sugiro dividir todos os números por alguma constante, por ex.1000 e depois multiplicá-los novamente.(Se esta constante dividir todos os números de entrada, a solução permanecerá ótima.)

Answer 2

Se você tivesse apenas uma tag, isso se tornaria um problema de mochila:em particular, determinar se você poderia vender todas as impressões seria exatamente o problema do subconjunto.Portanto, o problema é NP-difícil.

Uma abordagem plausível para resolvê-lo na prática seria usar programação linear inteira.