Algoritmo de optimización de distribución

Question

Estoy tratando de clasificar y encontrar una solución razonable para el siguiente problema (abstraído de un problema del mundo real).

Problema

Imagine que StackOverflow comenzó a ofrecer una suscripción donde las empresas podían comprar X cantidad de impresiones por mes para un conjunto de etiquetas.

Por ejemplo, es posible que le interese publicar un anuncio con 50 000 impresiones en las siguientes etiquetas: javascipt, typescript, react, nextjs, nodejs, webpack.

StackOverflow "promete" que obtendrá 50000 impresiones, pero son libres de distribuirlas entre las etiquetas anteriores como deseen (incluso podría ser el 100% en una etiqueta).

¿Cómo debería StackOverflow optimizar la distribución para que puedan vender/entregar la cantidad máxima de impresiones?

Para simplificar, supongamos:

• Sabemos de antemano el número de impresiones que recibe cada etiqueta por mes y no cambia.
• cada impresión solo pertenece a una única etiqueta

Mi investigación

Creo que esto podría ser similar al Mochila o embalaje del contenedor problemas.

La forma más sencilla de abordar esto es con un algoritmo de "primero en llegar" (o tal vez mejor descrito como "primero en llegar, primero en servir"):

1. Obtenga todas las "suscripciones" activas (impresiones y etiquetas), ordenadas por fecha de creación ASC
2. Para cada "suscripción", toma la primera etiqueta y "consume" tantas impresiones como podamos.Si a la suscripción aún le quedan impresiones, pase a la siguiente etiqueta.
3. Repetir con la próxima suscripción

Eso podría resultar algo como esto:

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

La optimización de esta solución es claramente horrible.En el ejemplo anterior, si bien teníamos impresiones más que suficientes para todos, asignamos las únicas que "Stark" podía comprar antes de llegar a ellas.

¿Existe un nombre oficial para este problema y cuál es la solución óptima?

Answer 1

Creo que esto es en realidad "sólo" una coincidencia bipartita de cardinalidad máxima, que se puede resolver de manera óptima en $O(|E|\sqrt{|V|})$ tiempo usando el Algoritmo de Hopcroft-Karp.

En un lado, tiene un vértice para cada impresión solicitada (digamos, el cliente A exige 50000 de "javascript" o "mecanografiado", y el cliente B exige 10000 "javascript", por lo que 60000 vértices en total), y en el otro lado tiene un vértice para cada impresión proporcionada (digamos, 30000 etiquetados como "javascript" y 15000 etiquetados como "mecanografiado", es decir, 45000 vértices en total).Dibuje una arista de cada impresión solicitada a cada impresión suministrada de un tipo que satisfaga sus restricciones de tipo de impresión (por lo que habría 45.000 aristas saliendo de cada uno de los vértices del cliente A y 15.000 aristas saliendo de cada uno de los clientes B) y resuelva.

Si tiene miles de impresiones, puede terminar con millones de aristas, lo que puede llevar demasiado tiempo.Si una respuesta aproximada es suficiente, sugeriría dividir todos los números por alguna constante, por ejemplo.1000, y luego volver a multiplicarlos.(Si esta constante divide todos los números de entrada, la solución seguirá siendo óptima).

Answer 2

Si solo tuvieras una etiqueta, esto se convertiría en un problema de mochila:en particular, determinar si se podrían vender todas las impresiones sería exactamente el problema del subconjunto.Por tanto, el problema es NP-difícil.

Un enfoque plausible para resolverlo en la práctica sería utilizar programación lineal entera.