Algoritmi randomizzati: alta probabilità rispetto all'aspettativa

Question

Speriamo che questa domanda non sia troppo generale, ma mi stavo chiedendo cosa sia la relazione tra algoritmi randomizzati che si comportano bene con alta probabilità e coloro che si comportano bene in attesa. La mia domanda è motivata dalla definizione di una $ \ alpha $ algoritmo -approssimazione data qui , vale a dire che è un algoritmo poligomiale che produce una soluzione all'interno di $ \ alfa $ di opt in attesa o con alta probabilità. Ho anche scoperto che le prime pagine di Questa fonte fornisce una buona visione degli approcci di attesa dell'alta probabilità rispetto all'aspettativa, ma ho ancora domande.

.
• Puoi sempre trasformare un algoritmo che raggiunge una $ \ alfa $ -approssimazione in attesa a uno che lo raggiunge con alta probabilità, e viceversa? (Apparentemente recuperando l'algoritmo multiplo [un numero polinomiale] di volte.)
• In caso contrario, è più difficile dell'altro da ottenere? (Penserei che se risolvi $ \ alpha $ , un algoritmo ad alta probabilità sarebbe sempre più difficile da trovare / meno probabilità di trovare. O forse puoi sempre trovare uno, ma il rapporto di approssimazione diventerà peggiore.)

Grazie per l'aiuto!

Answer 1

Se si dispone di un algoritmo che è una classe $ \ alfa $ -approssimazione in attesa, quindi è possibile costruire un algoritmo che è una $ (1+ \ Epsilon) \ Alpha $ -approximazione con alta probabilità, per qualsiasi classe $ \ Epsilon> 0 $ . In particolare, dalla disuguaglianza di Markov, se si esegue l'algoritmo, quindi con probabilità almeno $ 1-1 / (1+ \ epsilon) $ emetterà una classe $ (1+ \ Epsilon) \ Alpha $ -approssimazione. Quindi, se si esegue l'algoritmo circa $ (c \ log n) / \ epsilon $ volte e mantenere la migliore uscita tra tutte quelle prove, con probabilità circa $ 1-1 / n ^ c $ troverai una $ (1+ \ epsilon) \ alfa $ -approssimazione .

Se si dispone di un algoritmo che è una classe $ \ alfa $ -approximazione con alta probabilità, non ci sono garanzie sull'aspettativa. È possibile che con probabilità molto piccola (probabilità $ 1 / n ^ c $ ), emette una soluzione estremamente negativa (una con fattore di approssimazione esponenzialmente grande), e in tutti gli altri Casi Emette una classe $ \ alfa $ -approssimazione. In questo caso, il valore atteso del fattore di approssimazione sarà molto grande, anche se ha una probabilità molto piccola di emettere una soluzione così negativa.