Approximation algorithm

for NP-complete problems (VLSI, biology) in poly time, algo finds a solution that isn’t necessarily optimal but is close to optimal $C_{OPT}$: optimal; $C_A$: approximate

we want, where $p(n)$ is an error bound

$$\max \left(\frac{C_A}{C_{OPT}},\frac{C_{OPT}}{C_A}\right)\le p(n)$$

first fraction is a minimisation bound, second is a maximisation so if $p(n)=2$, then we might want $C_A\le 2C_{OPT}$

some families of approximation algos

• fixed error bound
• variable error bound: as $n$ increases, allowable error can increase too
• trade-off between $p(n)$ and time

many approximation algorithms are greedy

basic approximation algo for vertex cover: very simple! pick vertex, erase edges, etc

C = 0, E' = E
while E' != \emptyset
	randomly pick (u, v) edge
		C = C \cup {u, v}
		E' = E' - {edges adjacent to u, v}

we can prove: this gives us not worse than twice the size of the optimal vertex cover

theorem: approximate vertex cover $C_A\le 2C_{OPT}$ let $A$ be selected edges $C_A=2A$, bc for every edge we include the vertex of the edge $A\le C_{OPT}$, this holds bc vertex cover then $C_A\le 2C_{OPT}$