Algoritmos aleatorios: alta probabilidad vs. expectativa

Question

Esperemos que esta pregunta no sea demasiado general, pero me preguntaba cuál es la relación entre los algoritmos aleatorios que se desempeñan bien con la alta probabilidad y los que desempeñan bien en la expectativa. Mi pregunta está motivada por la definición de una $ \ alfa $ -Aproximation algoritmo dado aquí , a saber, que es un algoritmo de tiempo polinomial que produce una solución dentro de $ \ Alpha $ de opt in expectativa o con alta probabilidad. También encontré que las primeras páginas de Esta fuente proporciona una buena idea de los enfoques de alta probabilidad frente a las expectativas, pero todavía tengo preguntas.

• ¿Puede siempre transformar un algoritmo que logra un $ \ alfa $ -Aproximation en la expectativa de uno que logre esto con alta probabilidad y viceversa? (Ostensiblemente al reacerse al algoritmo múltiple [un número polinomio] de veces).
• Si no, ¿es uno más difícil que el otro para obtener? (Pensaría que si arreglas $ \ alfa $ , un algoritmo de alta probabilidad siempre sería más difícil encontrar / menos probabilidades de existir. O tal vez siempre puedes encontrar uno, pero la relación de aproximación se volverá peor.)

¡Gracias por la ayuda!

Answer 1

Si tiene un algoritmo que es un $ \ alfa $ -Aproximation en la expectativa, entonces puede construir un algoritmo que sea un $ (1+ \ Epsilon) \ Alpha $ -Aproximation con alta probabilidad, para cualquier $ \ epsilon> 0 $ . En particular, por la desigualdad de Markov, si ejecuta el algoritmo, luego con probabilidad al menos $ 1-1 / (1+ \ epsilon) $ emitirá una $ (1+ \ Epsilon) \ Alpha $ -Aproximation. Por lo tanto, si ejecuta el algoritmo sobre $ (c \ log n) / \ epsilon $ veces y mantenga la mejor salida entre todas esas pruebas, con probabilidad de $ 1-1 / n ^ C $ Usted encontrará un $ (1+ \ epsilon) \ alfa $ -apoximation .

Si tiene un algoritmo que es un $ \ alfa $ -Aproximation con alta probabilidad, no hay garantías sobre la expectativa. Es posible que con una probabilidad muy pequeña (probabilidad $ 1 / n ^ C $ ), emite una solución extremadamente mala (una con un factor de aproximación exponencialmente grande), y en todos los demás Casos que produce un $ \ alfa $ -apoximation. En este caso, el valor esperado del factor de aproximación será muy grande, aunque tenga una probabilidad muy pequeña de generar una solución tan mala.