Gewichtetes Online-Matching - randomisierte Algorithmen

Question

Betrachten wir das randgewichtete Online-Matching-Problem.

Die Scheitelpunkte kommen online an und zeigen alle ihre aktuellen Kanten und Kantengewichte $ w_e> 0 $ .Ziel ist es, das Gewicht der Übereinstimmungen zu maximieren.Eine Kante kann nur einmal ein- und unwiderruflich zum Anpassen hinzugefügt werden.Wie oft erwägen wir, dass wir die Einstellung von KVV in Betracht ziehen.

Es ist offensichtlich, dass jeder deterministische Algorithmus nicht gegen einen nicht gängigen Gegner wettbewerbsfähig sein kann.Da könnte jeder neue Rand willkürlich großes Gewicht sein.

kann ein randomisierter Algorithmus auf dieses Ergebnis verbessern?

Answer 1

Ein randomisierter Algorithmus kann in der Worst-Case-Reihenfolge nicht konstant konkurrenzfähig sein. Ein Beweis mithilfe von YAOs Prinzip kann gefunden werden hier .