Approximation algorithms

LP based Approximation algorithms

Rephrase (maybe NP hard) problem as Integer Programming problem; Make LP relaxation; solve in polytime; translate solution by rounding; make $(\delta ,ϵ)$ approximation guarantees. Rounding choices: To closest integer, or randomized rounding.

Vertex cover problem

G=(V,E). IP: Vars $v_i$ = 0 or 1, $\mathrm{\forall }(i,j)\in E,v_i+v_j\ge 1$, $min\sum v_i=?$; LP relaxation: \(\hat{v}{i} \in [0,1]\); solution \(\sum \hat{v}{i} \leq opt \leq \sum v_{i}\); round to nearest int to get approx soln $\left\{v_i\right\}$; as \(v_{i} \leq 2 \hat{v}{i}\): \(\sum v{i} \leq 2 opt\).

Max SAT.

\tbc

Semidefinite programming based approximation algs

\tbc