6 Approximation and Randomized Algorithm

Approximation

An optimization (minimization) problem is called $\epsilon$-approximable if there exists a polynomial time algorithm that outputs a solution of cost $C$, when the optimal cost is $C^*$, and $\frac{C}{C^*}\leq \epsilon$ or $\frac{C^*}C\leq \epsilon$

Randomized Algorithm

• Monte Carlo: runs in polynomial time always and output is correct with high probability
• Las Vegas: runs in expected polynomial time and output always correct