randomized algorithm

2023-12-05

algorithm

two types:

Las Vegas: Time complexity is probabilistic, correctness is deterministic example: randomized Quicksort
Monte Carlo:Time complexity is deterministic, correctness is probabilistic

Efficient deterministic algorithms that always yield the correct answer are a special case of efficient randomized algorithms that oly need to yield the correct answer with high probability.
证明存在某种情况或性质

####

probabilistic method

use the fact that a random algorithm produces them with probability p>0 to prove the existence of certain solutions.

expected approximation ratio

weighted Max Sat

4/3-approximative LP-based algorithm

Global Minimun Cut

there is a polynomial time algorithm to find a global min-cut in an undirected graph G

contraction algorithm(Karger)(Monte Carlo)

In the following figure, contracting the edges in the specified order, will find the min-cut. Note that in this case, we were lucky and did not contract the edges that were in the min-cut

this may not always give the minimum cut if the algorithm picks an edge from the actual minimum cut
The contraction algorithm returns a min cut with prob >=2/$n^2$
IF we repeat the contraction algorithm $n^2$ln$n$ times,then the probability of failing to find the global min-cut is <1/$n^2$

max 3-SAT

Given a 3-SAT formula with k clauses, the expected number of clauses satisfied by a random assignment is 7k/8

max-cut

quick sort

we can only guarantee to have the pivot in its correct location because we don’t sort the other elements. Instead, we move them to the left or right of the pivot. Finally, we perform two recursive calls. The first call sorts the elements before the pivot, while the other sorts the ones after.

Best-Case Scenario

if we keep dividing the array in half, we’ll end up with the minimum number of recursion levels, which is {O(log(n))}
Since in each level, we perform O(n) comparisons to put the pivot in its correct location, then the overall complexity in the best-case scenario is O(nlog(n)).