Randomisierte Algorithmen: High-Wahrscheinlichkeit vs. Erwartung

Question

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 $ \ alpha $ -Apprximationsalgorithmus gegeben hier , nämlich ein Polynom-Zeitalgorithmus, der eine Lösung innerhalb von $ \ alpha $ von entwurf in Erwartung oder mit hoher Wahrscheinlichkeit. Ich stellte auch fest, dass die ersten Seiten von Diese Quelle bietet einen guten Einblick in die High-Wahrscheinlichkeit gegenüber der Erwartungsansätze, aber ich habe immer noch Fragen.

.
• 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!

Answer 1

Wenn Sie einen Algorithmus haben, der ein $ \ alpha $ -Approximation in Erwartung ist, können Sie einen Algorithmus erstellen, der eine $ (1+ \ Epsilon) \ alpha $ -Approximation mit hoher Wahrscheinlichkeit, für jeden $ \ Epsilon> 0 $ . Insbesondere durch Markovs Ungleichheit, wenn Sie den Algorithmus ausführen, dann mit der Wahrscheinlichkeit mindestens $ 1-1 / (1+ \ Epsilon) $ Es wird eine $ (1+ \ Epsilon) \ alpha $ -Approximation. Wenn Sie also den Algorithmus über $ (C \ log n) / \ Epsilon $ Times ausführen, und halten Sie die beste Ausgabe zwischen all diesen Studien, wobei die Wahrscheinlichkeit von $ 1-1 / n ^ C $ Sie finden einen $ (1+ \ Epsilon) \ alpha $ -Apprximation .

Wenn Sie einen Algorithmus haben, der ein $ \ alpha $ -Approximation mit hoher Wahrscheinlichkeit ist, gibt es keine Garantie für die Erwartung. Es ist möglich, dass mit sehr geringer Wahrscheinlichkeit (Wahrscheinlichkeit $ 1 / n ^ C $ ) eine extrem schlechte Lösung ausgibt (eines mit exponentiell großem Annäherungsfaktor) und in allen anderen Koffer gibt es einen $ \ alpha $ -Approximation aus. In diesem Fall ist der erwartete Wert des Näherungsfaktors sehr groß, auch wenn es eine sehr geringe Wahrscheinlichkeit hat, eine solche schlechte Lösung auszugeben.