Übereinstimmende Scheitelpunkte mit der Summe der Kantengewichte auf dem Bippartit-Diagramm

Question

Anfang dieser Woche fragte ich (bitte überprüfen): < / p>

Imagine stackoverflow beginnt mit einem Abonnement, in dem Unternehmen könnte X-Anzahl von Impressionen pro Monat für einen Satz von Tags kaufen.

Sie möchten beispielsweise daran interessiert, eine Anzeige mit 50000 zu betreiben Impressionen in den folgenden Tags: Javafipt, Tastercript, reagieren, nextjs, nodejs, webpack.

stackoverflow "verspricht" erhalten Sie 50000 Eindrücke, aber sie sind frei, sie über die obigen Tags zu verteilen, jedoch wünschen sie sich (könnte sogar 100% zu einem Tag sein).

Eine der Lösungen, die mit dem Hopcroft-Karp-Algorithmus bereitgestellt wird, den ich seitdem erfolgreich gewesen bin implementieren.

Ich habe jedoch Probleme, diese Lösung zu skalieren, um für meinen Anwendungsfall zu arbeiten. Der Flaschenhals ist eigentlich im Setup des Diagramms mehr-so als die Algorithmusleistung.

Das Problem ist die massive Anzahl von Kanten, die initialisiert werden müssen. Machen Sie das Beispiel unten:

generasacodicetagpre.

Wenn wir einen Scheitelpunkt erstellen, um jedes Gerät darzustellen, enden wir mit einem Diagramm mit 101 Kanten (7 * 11 + 4 * 6)!

Das Problem, an dem ich arbeite, ist Größenordnungen größer, so dass dies schnell unrealistisch wird.

Wie vermuten lassen, kann ich die Anzahl der Scheitelpunkte reduzieren, indem ich die Einheiten skaliert, aber ich verliere die Lösung, und das ist in diesem Fall tatsächlich etwas wichtig (ich kann vielleicht um 100x max.).

Ich dachte, es muss ein effizienteres Weg sein, dies zu tun, da ich im Wesentlichen Vertex für jede Einheit duplizierst. Ich kam mit dem folgenden virtitären Diagramm mit gewichteten Kanten und Scheitelpunkten auf:

Das Ziel wäre es, die Gewichte der Kanten so einzustellen, dass:

• Auf der linken Seite ist die Summe der Kanten dem Wert des Scheitelpunkts
• Rechts ist die Summe der Kanten weniger als oder gleich dem Wert des Scheitelpunkts

ist ein Beispiel einer der Lösungen:

Ich vermute (hoffen) Dies ist bereits ein bekannter Problem, für den es auch eine gut dokumentierte Lösung gibt (idealerweise eine, die nicht np-hart ist)!

Vielleicht ist es sogar möglich, den Hopcroft-Karp-Algorithmus zu ändern, um dafür zu arbeiten?

Answer 1

Ich habe schlechte Nachrichten. Es gibt keine Hoffnung auf einen Algorithmus, dessen schlimmste Laufzeit in der Größe des gewichteten Diagramms Polynom ist (es sei denn, p= NP, was unwahrscheinlich erscheint).

Ihr Problem ist so hart wie das Rucksackproblem, das keinen Polynom-Zeitalgorithmus aufweist (sofern der Eingang nicht in binärisiert dargestellt ist. Das Rucksackproblem hat einen Pseudopolynomialzeitalgorithmus, was bedeutet, dass es einen Algorithmus gibt, dessen Laufzeit in den Zahlen Polynom ist (aber keine Polynomzeit in der Größe des Eingangs). In Ihrer Umgebung verwandelt sich in einem Algorithmus, dessen Laufzeit Polynom in der Größe des ungewichteten Graphen (mit einer massiven Anzahl von Kanten) ist, jedoch nicht Polynom in der Größe des gewichteten Graphen (mit einer kleinen Anzahl von Kanten).

Sie könnten versuchen, dies als Integer-Linear-Programmierung (ILP) -Tinstanz auszudrücken, und dann mit einem ILP-Solver lösen. Es ist möglich, dass dies eine effizientere Lösung ergibt. Die Kernidee besteht darin, eine ganzzahlige Variable $ X_ {i, j} $ einzuführen, die die Anzahl der Eindrücke des Unternehmens enthält $ i $ in Tag $ J $ ; Dann können Sie ein paar lineare Ungleichheiten einführen, um die Anforderungen der Probleme aufzunehmen.