Randomized Algorithms

Randomized Algorithms and approximation algorithm

A randomized algorithm is an algorithm that uses randomness to
make some of its choices.

Las Vegas Algorithms

A Las Vegas algorithm is a randomized algorithm that always finds
the correct answer, but the running time of the algorithm might
vary significantly depending on the random choices made.

Monte Carlo Algorithms

A Monte Carlo algorithm is a randomized algorithm where the
output of the algorithm may be incorrect, but we have a guarantee
that this only happens with small probability.

Random Number Generator

True RNG: gets randomness from measuring physical phenomena
(e.g. background radiation) that we believe is sufficiently random
Pseudo-RNG: starting from a small random seed, new numbers are
generated in a completely deterministic way.

Randomized Min-Cut Algorithm

while G has more than 2 vertices:Pick a uniformly random edge of G and contract it.
the total runtime is $O(n^2m)$. However this algorithm can be refined and running time improved to $O(n^2log(n))$ (relatively simple algorithm) or
$O(m log^3(n))$ (more complicated algorithm).

approximation algorithm

The Maximum Cut Problem

Partition of vertices of G into two non-empty sets A and B such that number of edges between A and B is maximized. It is a NP-hard problem. Let us lower the ambition and try to find a fast algorithm that finds a “reasonably good” cut: Random algorithm:Put each vertex in either A or B independently with probability 1/2.The random assignment algorithm cuts (in expectation) at least half of all the edges in the graph.This is an example of an approximation algorithm.

finding “good but maybe not optimal” solutions

Heuristic Algorithms

Work well in some or even many cases, but with no guarantees
about how well they perform.

Approximation Algorithms

Algorithms with provable guarantee that the solution found is relatively good compared to the optimum solution, for all instances.
For a minimization problem, an algorithm has approximation ratio $\alpha ≥ 1$ if for every instance it holds that $ Alg ≤ \alpha Opt$.
For a maximization problem, the inequality goes the other way: we have approximation ratio $\alpha ≤ 1$ if $ Alg ≥ \alpha Opt$.

alpha-approximation algorithm

approximation ratio: $\alpha$.

Minimum Load Balancing

NP-hard problem.
Given Lengths t1; : : : ; tn of n jobs to be run on m machines, to find Minimum possible makespan of a schedule for the n jobs.
Approximation Algorithm for Load Balancing:Assign job i to the machine j with the smallest load.

how to prove it

The main difficulty in analyzing approximation
algorithms is to get some handle on the Opt value. We need to find Opt, but finding Opt is NP-hard, so we find lower bounds on Opt.

Minimum Vertex Cover

A vertex cover in a graph G is a set of vertices that “touches” every edge of G.What is the size of a minimum vertex cover of G? Approximation Algorithm for Minimum Vertex Cover:while there exists an edge e = (u; v) such that u /∈ S and v /∈ S, add (u,v) into S. The algorithm is a 2-approximation algorithm.
“Unique Games Conjecture”: it is known that Vertex Cover cannot be approximated better than
within a factor 2.

Minimum Set Cover

A collection of sets S1; : : : ; Sm ⊆ U over some universe U, What is minimum number of Si’s whose union equals U?

Analysis of Greedy Set Cover Finale?