Lösen Sie das online ungewichtete 0-1-Rucksackproblem effizient

Question

Ich habe $ N $ Elemente und ein Bin mit Größe $ B $ Einheiten. Jeder Artikel $ J $ Verbraucht $ w_j $ Einheiten $ B $ Wenn Sie in den Knapsack gelegt werden. Der Artikel erscheint online eins nacheinander. Sobald Artikel $ I $ erscheint, müssen wir ihn entweder in den Bin (unwiderruflich) setzen oder ignorieren. Ziel ist es, die Anzahl der in den Behälter eingesetzten Elemente zu maximieren. (Alle Eingänge sind positive Ganzzahlen.)

Der Offline-Algorithmus ist einfach: Platzieren Sie die Elemente in der Reihenfolge $ W_1 \ LEQ W_2 \ LEQ \ CDS \ LEQ W_N $ , bis der Fach voll ist.

Wie kann ich dieses Problem auf Online-Mode lösen? Mein Ansatz besteht darin, die Auswahlmöglichkeiten zu randomisieren: Sobald der Artikel $ J $ erscheint, geben Sie es mit der Wahrscheinlichkeit in den Behälter $ p_j $ < / span> und ignorieren Sie es anders.

Answer 1

Nun, wie Sie bereits bemerkt haben oder zumindest nicht erwähnt haben, ist es leicht zu sehen, dass es keinen deterministischen Wettbewerbsalgorithmus für Ihr Problem gibt.(Gegenexamples benötigen nur zwei Elemente, und Sie können die Tatsache verwenden, dass der Algorithmus deterministisch ist.)

Ihr Ansatz, der Randomisierung nimmt, eigentlich eigentlich eignen sich eigentlich nicht, da einige Schwierigkeiten nicht durch Randomisierung überwunden werden können.Es gibt jedoch ein paar Entspannungsmodelle Ihres Problems.

Einige davon, und einige Details zu meiner Antwort finden Sie in der Zeitung von Susanne Albers, Arindam Khan und Leon Ladewig mit dem Namen "Verbesserte Online-Algorithmen für Knapsack und Lücke im Zufallsbestellmodus" (siehe Abschnitt 1.1).