Algorithmes randomisés: une probabilité élevée vs attente

Question

Espérons que cette question n'est pas trop générale, mais je me demandais quelle est la relation entre des algorithmes randomisés qui fonctionnent bien avec une probabilité élevée et ceux qui fonctionnent bien dans l'attente. Ma question est motivée par la définition d'une catégorie $ \ alpha $ -approximation algorithme donnée ici , à savoir qu'il s'agit d'un algorithme de temps polynomial qui produit une solution dans $ \ alpha $ d'opter dans l'attente ou avec une probabilité élevée. J'ai aussi trouvé que les premières pages de Cette source offre une bonne idée de la probabilité élevée par rapport aux approches de l'attente, mais j'ai toujours des questions.

• Pouvez-vous toujours transformer un algorithme qui atteint un $ \ alpha $ -approximation dans l'attente d'une atteinte à une probabilité élevée, et inversement? (Extensiblement en respectant l'algorithme multiple [un nombre polynomial] de fois.)
• sinon, est un plus difficile que l'autre pour obtenir? (Je penserais que si vous réparez $ \ alpha $ , un algorithme de probabilité élevé serait toujours plus difficile à trouver / moins susceptible d'exister. Ou peut-être que vous pouvez toujours trouver un, mais le ratio approximatif va pire.)

Merci pour l'aide!

Answer 1

Si vous avez un algorithme qui est une $ \ alpha $ -approximation dans l'attente, vous pouvez alors construire un algorithme qui est une $ (1+ \ epsilon) \ alpha $ -approximation avec une probabilité élevée, pour tout $ \ epsilon> 0 $ . En particulier, par l'inégalité de Markov, si vous exécutez l'algorithme, alors avec probabilité au moins 1-1 $ / (1+ \ epsilon) $ il sortira une classe $ (1+ \ epsilon) \ alpha $ -approximation. Donc, si vous exécutez l'algorithme à propos de $ (c \ journal n) / \ epsilon $ fois et gardez la meilleure sortie parmi tous ces essais, avec une probabilité de $ 1-1 / N ^ C $ Vous trouverez une $ (1+ \ epsilon) \ alpha $ -approximation .

Si vous avez un algorithme qui est une $ \ alpha $ -approximation avec une probabilité élevée, il n'y a aucune garantie quant à l'attente. Il est possible qu'avec une très petite probabilité (probabilité 1 / N ^ C $ ), il génère une solution extrêmement mauvaise (une avec un facteur d'approximation exponentiellement important), et dans tous les autres Cases IT SUITES UNE SUITE UNE $ \ alpha $ -approximation. Dans ce cas, la valeur attendue du facteur d'approximation sera très grande, même s'il a une très petite probabilité de produire une telle solution.