Randomisierte Algorithmen: High-Wahrscheinlichkeit vs. Erwartung
-
29-09-2020 - |
Frage
Hoffentlich ist diese Frage nicht allgemein, aber ich habe mich gefragt, was die Beziehung zwischen randomisierten Algorithmen ist, die gut mit hoher Wahrscheinlichkeit und denjenigen, die in Erwartung gut funktionieren, gut funktionieren. Meine Frage ist motiviert durch die Definition eines randomisierten
- .
- Können Sie einen Algorithmus immer umwandeln, der einen
$ \ alpha $ -Approximation in Erwartung an einen erreicht, der dies mit hoher Wahrscheinlichkeit erreicht, und umgekehrt? (Angeblich durch den neuwerbenden Algorithmus mehrfach [eine Polynomanzahl] der Zeiten.) - Wenn nicht, ist ein härter als der andere, um zu erhalten? (Ich denke, dass, wenn Sie $ \ alpha $ , ein High-Wahrscheinlichkeitsalgorithmus, immer schwerer sein würde, immer schwieriger zu finden / weniger wahrscheinlich zu sein. Oder vielleicht können Sie immer finden eins, aber das Annäherungsverhältnis wird schlechter.)
Danke für die Hilfe!
Lösung
Wenn Sie einen Algorithmus haben, der ein
Wenn Sie einen Algorithmus haben, der ein