Algoritmi randomizzati: alta probabilità rispetto all'aspettativa
-
29-09-2020 - |
Domanda
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!
Soluzione
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.