Maximizing the Probability of Randomized Algorithms

Question

I work in the field of computer science, and I just participate in the finals. I ran into a problem that was inadequate with various problems such as dynamic programming. I will summarize:

I have been given an efficient randomized algorithm A that returns an independent set. This algorithm returns the maximum independent set with a probability of at least 1 / (n ^ 3), where n is the number of vertices in the graph. Suggest another algorithm using A, which returns the maximum set with a probability of at least 1/2.

I studied randomized algorithms, but it just looks like a simple implementation case. If I were to run A n ^ 3 times, the probability that the maximum independent set is close to 1. Can I say that doing it n ^ 3/2 times will give the desired effect? Am I just trying to make it harder? Any help is appreciated.

Answer 1

Close, but not exactly, the probability that one of the runs will return the correct answer is at least 1 / n ^ 3. This means that the probability of receiving the wrong answer in one pass is (1-1 / n ^ 3), which means that the probability of getting the correct answer after M runs is 1- (1-1 / n ^ 3) ^ M.

e ( ), n ^ 3 , 1-1/e, , 1/2 ( 1), , 1/2 - (n ^ 3) * ln (2).

Answer 2

, . , .

A n ^ 3, n ^ 3 . . n ^ 3? , .

( ), , , , , O (n ^ 3).