Algorithmus zur Verteilungsoptimierung

Question

Ich versuche, das folgende Problem zu klassifizieren und eine vernünftige Lösung zu finden (abstrahiert von einem realen Problem).

Problem

Stellen Sie sich vor, StackOverflow würde ein Abonnement anbieten, bei dem Unternehmen X Impressionen pro Monat für eine Reihe von Tags kaufen könnten.

Beispielsweise könnten Sie daran interessiert sein, eine Anzeige mit 50.000 Impressionen auf den folgenden Tags zu schalten: javascipt, typescript, react, nextjs, nodejs, webpack.

StackOverflow „verspricht“, dass Sie 50.000 Impressionen erhalten werden, es steht ihnen jedoch frei, diese nach Belieben auf die oben genannten Tags zu verteilen (es könnte sogar 100 % auf ein Tag sein).

Wie sollte StackOverflow die Verteilung optimieren, damit die maximale Anzahl an Impressionen verkauft/ausgeliefert werden kann?

Nehmen Sie der Einfachheit halber an:

• Wir kennen die Anzahl der Impressionen, die jedes Tag pro Monat erhält, im Voraus und ändern sich nicht
• Jede Impression gehört nur zu einem einzelnen Tag

Meine Forschung

Ich glaube, das könnte ähnlich sein Tornister oder Behälterverpackung Probleme.

Der einfachste Weg, dies zu erreichen, ist ein „First-Fit“-Algorithmus (oder vielleicht besser beschrieben als „Wer zuerst kommt, mahlt zuerst“):

1. Erhalten Sie alle aktiven „Abonnements“ (Impressionen und Tags), sortiert nach Erstellungsdatum (ASC).
2. Schnappen Sie sich für jedes „Abonnement“ das erste Tag und „verbrauchen“ Sie so viele Impressionen wie möglich.Wenn das Abonnement noch über verbleibende Impressionen verfügt, fahren Sie mit dem nächsten Tag fort.
3. Wiederholen Sie dies mit dem nächsten Abonnement

Das könnte etwa so ablaufen:

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

Die Optimierung für diese Lösung ist eindeutig schrecklich.Im obigen Beispiel hatten wir zwar mehr als genug Impressionen, um herumzugehen, aber wir haben die einzigen Impressionen zugewiesen, die „Stark“ kaufen konnte, bevor wir zu ihnen kamen.

Gibt es einen offiziellen Namen für dieses Problem und wie sieht die optimale Lösung aus?

Answer 1

Ich denke, das ist eigentlich „nur“ ein bipartites Matching mit maximaler Kardinalität, das optimal gelöst werden kann $O(|E|\sqrt{|V|})$ Zeit mit der Hopcroft-Karp-Algorithmus.

Auf der einen Seite haben Sie einen Scheitelpunkt für jede angeforderte Impression (beispielsweise verlangt Kunde A 50.000 „Javascript“ oder „Typescript“ und Kunde B verlangt 10.000 „Javascript“, also insgesamt 60.000 Scheitelpunkte), und auf der anderen Seite Sie haben einen Scheitelpunkt für jeden bereitgestellten Eindruck (z. B. 30.000 mit der Bezeichnung „Javascript“ und 15.000 mit der Bezeichnung „Typoskript“, also insgesamt 45.000 Scheitelpunkte).Zeichnen Sie eine Kante von jedem angeforderten Abdruck zu jedem bereitgestellten Abdruck eines Typs, der seine Abdrucktypbeschränkungen erfüllt (es würden also 45.000 Kanten vorhanden sein, die jeden Scheitelpunkt von Kunde A verlassen, und 15.000 Kanten, die jeden Scheitelpunkt von Kunde B verlassen), und lösen Sie die Lösung.

Wenn Sie Tausende von Abdrücken haben, erhalten Sie möglicherweise Millionen von Kanten, was möglicherweise zu lange dauert.Wenn eine ungefähre Antwort ausreicht, würde ich vorschlagen, alle Zahlen durch eine Konstante zu dividieren, z. B.1000 und anschließend wieder multiplizieren.(Wenn diese Konstante alle Eingabezahlen dividiert, bleibt die Lösung optimal.)

Answer 2

Wenn Sie nur ein Tag hätten, würde dies zu einem Rucksackproblem werden:Insbesondere wäre die Bestimmung, ob alle Impressionen verkauft werden könnten, genau das Teilmengenproblem.Daher ist das Problem NP-schwer.

Ein plausibler Lösungsansatz in der Praxis wäre die Verwendung einer ganzzahligen linearen Programmierung.